Złożoność spełniania ograniczeń

Złożoność spełniania ograniczeń to zastosowanie teorii złożoności obliczeniowej do spełniania ograniczeń . Był badany głównie pod kątem rozróżnienia między możliwymi do rozwiązania i trudnymi do rozwiązania klasami problemów spełniania ograniczeń w dziedzinach skończonych.

Rozwiązanie problemu spełnienia ograniczeń w domenie skończonej jest ogólnie problemem NP-zupełnym . Badania wykazały szereg podprzypadków czasu wielomianowego , w większości uzyskanych poprzez ograniczenie dozwolonych dziedzin lub ograniczeń lub sposobu nałożenia ograniczeń na zmienne. Badania ustaliły również związek między problemem spełniania ograniczeń a problemami w innych dziedzinach, takich jak skończona teoria modeli i bazy danych .

Przegląd

Ustalenie, czy problem spełnienia ograniczeń w dziedzinie skończonej ma rozwiązania, jest ogólnie problemem NP zupełnym. Jest to łatwa konsekwencja tego, że wiele innych problemów NP zupełnych można wyrazić jako problemy spełnienia ograniczeń. Takie inne problemy obejmują spełnialność zdań i trójkolorowalność .

Traktowalność można uzyskać, rozważając określone klasy problemów spełniania ograniczeń. Na przykład, jeśli dziedzina jest binarna i wszystkie ograniczenia są binarne , ustalenie spełnialności jest problemem wielomianowym, ponieważ ten problem jest równoważny z 2-SAT , który można rozwiązać. Badania wykazały szereg możliwych do rozwiązania przypadków podrzędnych. Niektóre z tych klas opierają się na ograniczeniu dozwolonych domen lub relacji, inne na ograniczeniu sposobu nakładania ograniczeń na zmienne, a jeszcze inne na obu rodzajach ograniczeń.

Jeden kierunek badań wykorzystywał zgodność między problemem spełniania ograniczeń a problemem ustalenia istnienia homomorfizmu między dwiema strukturami relacyjnymi. Ta korespondencja została wykorzystana do powiązania spełniania ograniczeń z tematami tradycyjnie związanymi z teorią baz danych .

Rozważany problem badawczy dotyczy istnienia dychotomii pomiędzy zbiorami ograniczeń. Jest to pytanie, czy zestaw ograniczeń zawiera tylko ograniczenia w czasie wielomianowym i ograniczenia NP-zupełne. To pytanie jest rozstrzygnięte dla niektórych zestawów ograniczeń, ale nadal otwarte dla zestawu wszystkich ograniczeń opartych na stałej domenie i zbiorze relacji, od 2007 r. Niektórzy autorzy uważają to za najważniejsze otwarte pytanie dotyczące złożoności spełniania ograniczeń .

Ograniczenia

Rozwiązywalne podprzypadki ogólnych problemów spełniania ograniczeń można uzyskać poprzez nałożenie odpowiednich ograniczeń na problemy. Rozważano różne rodzaje ograniczeń.

Ograniczenia strukturalne i relacyjne

Traktowalność można uzyskać poprzez ograniczenie możliwych domen lub ograniczeń. W szczególności rozważono dwa rodzaje ograniczeń:

• ograniczenia relacyjne ograniczają dziedzinę i wartości spełniające ograniczenia;
• ograniczenia strukturalne ograniczają sposób rozłożenia ograniczeń na zmienne.

Mówiąc dokładniej, ograniczenie relacyjne określa język ograniczeń , który jest domeną i zbiorem relacji w tej domenie. Problem spełniania ograniczeń spełnia to ograniczenie, jeśli ma dokładnie tę dziedzinę, a relacja każdego ograniczenia mieści się w danym zbiorze relacji. Innymi słowy, relacyjne ograniczenie ogranicza domenę i zestaw spełniających wartości każdego ograniczenia, ale nie ogranicza sposobu, w jaki ograniczenia są umieszczane na zmiennych. Zamiast tego odbywa się to za pomocą ograniczeń strukturalnych. Ograniczenie strukturalne można sprawdzić, patrząc tylko na zakresy ograniczeń (ich zmienne), pomijając ich relacje (ich zbiór wartości spełniających).

Język z ograniczeniami jest wykonalny, jeśli istnieje algorytm wielomianowy rozwiązujący wszystkie problemy w oparciu o język, to znaczy przy użyciu dziedziny i relacji określonych w domenie. Przykładem wykonalnego języka ograniczeń jest język domen binarnych i ograniczeń binarnych. Formalnie to ograniczenie odpowiada dopuszczeniu tylko dziedzin o rozmiarze 2 i tylko ograniczeń, których relacja jest relacją binarną. Podczas gdy drugi fakt implikuje, że zakresy ograniczeń są binarne, nie jest to ograniczenie strukturalne, ponieważ nie zabrania nakładania jakichkolwiek ograniczeń na dowolną parę zmiennych. Nawiasem mówiąc, problem staje się NP kompletny, jeśli jedno z ograniczeń zostanie zniesione: ograniczenia binarne i domeny trójskładnikowe mogą wyrażać kolorowania grafu , podczas gdy ograniczenia trójskładnikowe i domeny binarne mogą wyrażać 3-SAT ; oba te problemy są NP-zupełne.

Przykładem możliwej do rozwiązania klasy zdefiniowanej w kategoriach ograniczeń strukturalnych są binarne problemy acykliczne. Biorąc pod uwagę problem spełnienia ograniczeń tylko z ograniczeniami binarnymi, powiązany z nim wykres ma wierzchołek dla każdej zmiennej i krawędź dla każdego ograniczenia; dwa wierzchołki są połączone, jeśli są w wiązaniu. Jeśli wykres problemu jest acykliczny, problem również nazywamy acyklicznym. Problem spełnialności na klasie binarnego problemu acyklicznego jest wykonalny. Jest to ograniczenie strukturalne, ponieważ nie nakłada żadnych ograniczeń na dziedzinę ani na określone wartości, które spełniają ograniczenia; raczej ogranicza sposób nakładania ograniczeń na zmienne.

Podczas gdy ograniczenia relacyjne i strukturalne są najczęściej używane do wyprowadzenia możliwych do zastosowania klas spełniania ograniczeń, istnieją pewne możliwe do zastosowania klasy, których nie można zdefiniować tylko za pomocą ograniczeń relacyjnych lub tylko ograniczeń strukturalnych. Klasa traktowalna zdefiniowana pod względem wypukłości wierszy nie może być zdefiniowana tylko pod względem relacji lub tylko pod względem struktury, ponieważ wypukłość wierszy zależy zarówno od relacji, jak i od kolejności zmiennych (a zatem nie można jej sprawdzić, patrząc tylko na każde ograniczenie po kolei).

Jednolite i niejednolite ograniczenia

Podprzypadek uzyskany przez ograniczenie do języka z ograniczeniami skończonymi nazywany jest problemem niejednorodnym . Problemy te są najczęściej brane pod uwagę przy wyrażaniu satysfakcji z ograniczeń w kategoriach problemu homomorfizmu, jak wyjaśniono poniżej. Zdefiniowano również jednolite problemy w ustawieniach problemów homomorfizmu; jednolity problem można zdefiniować jako połączenie (prawdopodobnie nieskończonego) zbioru niejednorodnych problemów. Jednolity problem składający się z nieskończonego zestawu niejednorodnych problemów może być trudny do rozwiązania, nawet jeśli wszystkie te niejednorodne problemy są wykonalne.

Ograniczenia oparte na drzewie

Niektóre rozważane ograniczenia opierają się na możliwości rozwiązania problemu spełniania ograniczeń, w którym wszystkie ograniczenia są binarne i tworzą drzewo nad zmiennymi. Jest to ograniczenie strukturalne, ponieważ można je sprawdzić, patrząc tylko na zakresy ograniczeń, pomijając domeny i relacje.

Ograniczenie to opiera się na pierwotnym grafie problemu, który jest grafem, którego wierzchołki są zmiennymi problemu, a krawędzie reprezentują obecność ograniczenia między dwiema zmiennymi. Traktowalność można jednak również uzyskać, umieszczając warunek bycia drzewem na pierwotnym grafie problemów, które są przeformułowaniami pierwotnego.

Warunki równoważności

Problemy spełnienia ograniczeń można przeformułować w kategoriach innych problemów, co prowadzi do warunków równoważnych z wykonalnością. Najczęściej używanym przeformułowaniem jest problem homomorfizmu .

Spełnianie ograniczeń i problem homomorfizmu

Powiązanie spełniania ograniczeń z teorią baz danych zostało przedstawione w postaci zgodności problemu spełnialności ograniczeń z problemem sprawdzenia, czy istnieje homomorfizm między dwiema strukturami relacyjnymi. Struktura relacyjna jest matematyczną reprezentacją bazy danych: jest zbiorem wartości i zbiorem relacji między tymi wartościami. Formalnie $_$ _ $}}$$Displaystyle$$wartości$ jest relacją względem , czyli zbiorem krotek .

Struktura relacyjna różni się od problemu spełniania ograniczeń, ponieważ ograniczenie jest relacją i krotką zmiennych. Inny jest również sposób, w jaki są one używane: w przypadku problemu spełnienia ograniczeń głównym problemem jest znalezienie satysfakcjonującego przypisania; w przypadku struktury relacji głównym problemem jest znalezienie odpowiedzi na zapytanie.

Problem spełnienia ograniczeń jest jednak powiązany z problemem ustalenia istnienia homomorfizmu między dwiema strukturami relacyjnymi. Homomorfizm to funkcja od wartości pierwszej relacji do wartości drugiej, która zastosowana do wszystkich wartości relacji pierwszej struktury zamienia ją w podzbiór odpowiedniej relacji drugiej struktury. Formalnie ${\ displaystyle h}$ jest homomorfizmem z ${\ Displaystyle A = (V, R_ {1} ^ {A}, \ ldots, R_ {n } ^ {A})}$ do ${\ Displaystyle B = (D, R_ {1} ^ {B}, \ ldots, R_ {n} ^ {B })}$ jeśli jest to funkcja od do ${\ displaystyle$$D}$ taka, że ​​jeśli $Displaystyle (x_ {1}, \ ldots x_ {k}) \ w R_ {i} ^ {A}}$ wtedy ${\ Displaystyle (h (x_ {1}), \ ldots ,h(x_{k}))\in R_{i}^{B}}$ .

Można ustalić bezpośrednią zgodność między problemem spełnienia ograniczeń a problemem homomorfizmu. Dla zadanego problemu spełniania ograniczeń można zbudować parę struktur relacyjnych, z których pierwsza koduje zmienne i sygnatury ograniczeń, a druga domeny i relacje ograniczeń. Spełnialność problemu spełniania ograniczeń odpowiada znalezieniu takiej wartości dla każdej zmiennej, że zastąpienie wartości w sygnaturze powoduje, że jest ona krotką w relacji ograniczenia. Jest to możliwe dokładnie wtedy, gdy ta ocena jest homomorfizmem między dwiema strukturami relacyjnymi.

Odpowiedniość odwrotna jest odwrotna: mając dwie struktury relacyjne, jedna koduje wartości pierwszej w zmiennych problemu spełniania ograniczeń, a wartości drugiej w dziedzinie tego samego problemu. Dla każdej krotki każdej relacji pierwszej struktury istnieje ograniczenie, którego wartością jest odpowiednia relacja drugiej struktury. W ten sposób homomorfizm odpowiada odwzorowaniu każdego zakresu każdego ograniczenia (każdej krotki każdej relacji pierwszej struktury) na krotkę w relacji ograniczenia (krotka w odpowiedniej relacji drugiej struktury).

Problem spełniania ograniczeń niejednorodnych to ograniczenie, w którym ustalona jest druga struktura problemu homomorfizmu. Innymi słowy, każda struktura relacyjna definiuje niejednolity problem polegający na określeniu, czy struktura relacji jest wobec niej homomorficzna. Podobne ograniczenie można nałożyć na pierwszą strukturę; dla dowolnej ustalonej pierwszej struktury problem homomorfizmu jest wykonalny. Jednolity problem spełnienia ograniczeń jest arbitralnym ograniczeniem do zbiorów struktur dla pierwszej i drugiej struktury problemu homomorfizmu.

Łączna ocena zapytania i zawieranie

Ponieważ problem homomorfizmu jest równoważny ocenie zapytania koniunkcyjnego i zawieraniu zapytań koniunkcyjnych, te dwa problemy są również równoważne spełnieniu ograniczeń.

Dołącz do oceny

Każde ograniczenie może być postrzegane jako tabela w bazie danych , gdzie zmienne są interpretowane jako nazwy atrybutów, a relacją jest zbiór rekordów w tabeli. Rozwiązania problemu spełniania ograniczeń są wynikiem wewnętrznego łączenia tablic reprezentujących jego ograniczenia; zatem problem istnienia rozwiązań można przeformułować jako problem sprawdzenia, czy wynik wewnętrznego łączenia pewnej liczby tablic jest pusty.

Twierdzenia o dychotomii

Wiadomo, że niektóre języki z ograniczeniami (lub problemy niejednorodne) odpowiadają problemom rozwiązywalnym w czasie wielomianowym , a niektóre inne wyrażają problemy NP-zupełne . Jednak możliwe jest, że niektóre języki z ograniczeniami nie są żadnym z nich. Z twierdzenia Ladnera wiadomo , że jeśli P nie jest równe NP, to w NP istnieją problemy, które nie są ani wielomianowe, ani NP-trudne. Od 2007 roku nie wiadomo, czy takie problemy można wyrazić jako problemy z spełnieniem ograniczeń za pomocą języka z ustalonymi ograniczeniami. Gdyby języki Ladnera nie były wyrażalne w ten sposób, zbiór wszystkich języków z ograniczeniami można by dokładnie podzielić na języki definiujące czas wielomianowy i definiujące problemy NP-zupełne; to znaczy, ten zestaw wykazywałby dychotomię .

Częściowe wyniki są znane dla niektórych zestawów języków z ograniczeniami. Najbardziej znanym takim wynikiem jest twierdzenie Schaefera o dychotomii , które dowodzi istnienia dychotomii w zbiorze języków z ograniczeniami w domenie binarnej. Dokładniej, dowodzi, że ograniczenie relacji w domenie binarnej jest wykonalne, jeśli wszystkie jej relacje należą do jednej z sześciu klas, aw przeciwnym razie jest NP-zupełne. Bułatow udowodnił twierdzenie o dychotomii dla dziedzin trzech elementów.

Innym twierdzeniem o dychotomii dla języków z ograniczeniami jest twierdzenie Hell-Nesetrila, które pokazuje dychotomię dla problemów dotyczących ograniczeń binarnych z pojedynczą ustaloną relacją symetryczną. Z punktu widzenia problemu homomorfizmu każdy taki problem jest równoważny istnieniu homomorfizmu ze struktury relacyjnej do danego ustalonego grafu nieskierowanego (graf nieskierowany można uznać za strukturę relacyjną z pojedynczą binarną relacją symetryczną). Twierdzenie Hella-Nesetrila dowodzi, że każdy taki problem jest albo wielomianowy, albo NP-zupełny. Mówiąc dokładniej, problem jest wielomianowy, jeśli wykres jest 2-kolorowy, to znaczy jest dwudzielny , aw przeciwnym razie jest NP-zupełny.

Wystarczające warunki dla wykonalności

Niektóre wyniki złożoności dowodzą, że niektóre ograniczenia są wielomianowe, nie dowodząc, że wszystkie inne możliwe ograniczenia tego samego rodzaju są NP-trudne.

Dziennik danych

Wystarczający warunek wykonalności jest związany z wyrażalnością w Datalog . Boolowskie zapytanie Datalog podaje wartość logiczną zbioru literałów w danym alfabecie, przy czym każdy literał jest wyrażeniem w postaci ${\ Displaystyle L (a_ {1}, \ ldots, a_ {n})}$ ; w rezultacie zapytanie Boolean Datalog wyraża zestaw zestawów literałów, ponieważ można je uznać za semantycznie równoważne zbiorowi wszystkich zestawów literałów, które ocenia jako prawdziwe.

Z drugiej strony problem niejednorodny może być postrzegany jako sposób wyrażenia podobnego zbioru. Dla danego niejednorodnego problemu zestaw relacji, które mogą być użyte w ograniczeniach, jest ustalony; $_$ rezultacie _ Przykład tego niejednorodnego problemu można następnie zapisać jako zbiór literałów postaci ${\ Displaystyle R_ {i} (x_ {1}, \ ldots, x_ {n })}$ . Wśród tych instancji/zestawów literałów niektóre są zadowalające, a inne nie; to, czy zbiór literałów jest spełnialny, zależy od relacji, które są określone przez problem niejednorodności. Na odwrót, problem niejednorodny mówi, które zbiory literałów reprezentują instancje zadowalające, a które instancje niezadowalające. Gdy relacje zostaną nazwane, niejednorodny problem wyraża zbiór zbiorów literałów: tych związanych z spełniającymi (lub niespełniającymi) przypadkami.

Wystarczającym warunkiem wykonalności jest to, że niejednorodny problem jest rozwiązywalny, jeśli zbiór jego niespełnialnych przypadków można wyrazić za pomocą boolowskiego zapytania Datalog. Innymi słowy, jeśli zbiór zestawów literałów reprezentujących niezadowalające wystąpienia problemu niejednorodności jest również zbiorem zestawów literałów spełniających zapytanie Boolean Datalog, to problem niejednorodności jest możliwy do rozwiązania.

Lokalna spójność

Spełnialność można czasami ustalić, wymuszając formę lokalnej spójności , a następnie sprawdzając istnienie pustej domeny lub relacji z ograniczeniami. Jest to ogólnie poprawny, ale niekompletny algorytm niespełnialności: problem może być niespełnialny, nawet jeśli nie powstaje pusta dziedzina ani relacja ograniczeń. W przypadku niektórych form spójności lokalnej ten algorytm może również wymagać wykładniczego czasu. Jednak dla niektórych problemów i dla niektórych rodzajów spójności lokalnej jest to poprawne i wielomianowe.

Poniższe warunki wykorzystują pierwotny wykres problemu, który ma wierzchołek dla każdej zmiennej i krawędź między dwoma węzłami, jeśli odpowiednie zmienne podlegają ograniczeniu. Poniżej przedstawiono warunki dotyczące problemów spełniania ograniczeń binarnych, w których wymuszenie spójności lokalnej jest wykonalne i umożliwia ustalenie spełnialności:

1. wymuszanie spójności łuku, jeśli graf pierwotny jest acykliczny;
2. wymuszenie spójności łuku kierunkowego dla takiego uporządkowania zmiennych, które sprawia, że ​​uporządkowany wykres ograniczeń ma szerokość 1 (takie uporządkowanie istnieje wtedy i tylko wtedy, gdy graf pierwotny jest drzewem, ale nie wszystkie uporządkowania drzewa generują szerokość 1);
3. wymuszenie silnej spójności ścieżki kierunkowej dla uporządkowania zmiennych, które sprawia, że ​​graf pierwotny ma indukowaną szerokość 2.

Warunek rozszerzający ostatni dotyczy niebinarnych problemów spełniania ograniczeń. Mianowicie, dla wszystkich problemów, dla których istnieje uporządkowanie, które sprawia, że ​​graf pierwotny mający indukowaną szerokość jest ograniczony przez stałą i, wymuszenie silnej kierunkowej spójności i jest wykonalne i pozwala na ustalenie spełnialności.

Warunki oparte na drzewach

Problemy spełnienia ograniczeń złożone tylko z ograniczeń binarnych można postrzegać jako wykresy , gdzie wierzchołki są zmiennymi, a krawędzie reprezentują obecność ograniczenia między dwiema zmiennymi. Ten wykres jest nazywany wykresem Gaifmana lub wykresem pierwotnych ograniczeń (lub po prostu wykresem pierwotnym) problemu.

Jeśli pierwotny wykres problemu jest acykliczny, ustalenie spełnialności problemu jest problemem możliwym do rozwiązania. Jest to ograniczenie strukturalne, ponieważ można je sprawdzić, patrząc tylko na zakresy ograniczeń, pomijając ich relacje i dziedzinę. Graf acykliczny to las , ale zwykle zakłada się spójność ; w rezultacie zwykle brany jest pod uwagę warunek, że grafy pierwotne są drzewami .

Ta właściwość drzewiastych problemów spełniania ograniczeń jest wykorzystywana przez metody dekompozycji , które przekształcają problemy w równoważne, które zawierają tylko ograniczenia binarne ułożone w postaci drzewa. Zmienne tych problemów odpowiadają zbiorom zmiennych pierwotnego problemu; dziedzinę takiej zmiennej uzyskuje się, biorąc pod uwagę niektóre ograniczenia pierwotnego problemu, którego zakres jest zawarty w odpowiednim pierwotnym zbiorze zmiennych; ograniczenia tych nowych problemów reprezentują równość zmiennych zawartych w dwóch zbiorach.

Jeśli wykresem jednego takiego równoważnego problemu jest drzewo, problem można skutecznie rozwiązać. Z drugiej strony stworzenie jednego takiego równoważnego problemu może nie być wydajne z powodu dwóch czynników: potrzeby określenia połączonych efektów grupy ograniczeń na zbiór zmiennych oraz potrzeby przechowywania wszystkich krotek wartości, które spełniają daną grupę ograniczeń.

Warunek konieczny dla trakcyjności

Udowodniono warunek konieczny dla wykonalności języka z ograniczeniami opartego na uniwersalnym gadżecie . Uniwersalny gadżet to szczególny problem spełnienia ograniczeń, który został pierwotnie zdefiniowany w celu wyrażenia nowych relacji poprzez projekcję.

Uniwersalny gadżet

Relacja, której nie ma w języku z ograniczeniami, może być „symulowana” przez ograniczenia z wykorzystaniem relacji w języku. W szczególności nową relację można utworzyć, nakładając zestaw ograniczeń i używając tylko niektórych ich zmiennych. Jeśli wszystkie inne ograniczenia używają tylko tych zmiennych, ten zestaw ograniczeń zmusza te zmienne do przyjmowania tylko określonych wartości, praktycznie symulując nową relację.

Każdy problem spełniania ograniczeń i podzbiór jego zmiennych definiuje relację, która składa się ze wszystkich krotek wartości zmiennych, które można rozszerzyć na inne zmienne, tworząc rozwiązanie. Technicznie rzecz biorąc, tę zależność uzyskuje się przez rzutowanie relacji mającej rozwiązania w postaci wierszy na rozważane zmienne.

Uniwersalny gadżet opiera się na obserwacji, że każdą relację zawierającą $-$$krotki$ można zdefiniować, projektując relację zawierającą wszystkie możliwe kolumny elementów domeny Jako przykład, poniższe tabele przedstawiają taką projekcję:

abcdefghbd --------------- --- 1 1 1 1 0 0 0 0 -> 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0

$stronie$ jest zbiorem rozwiązań problemu spełnienia ograniczeń, jej zmienne są ograniczone do wartości z tabeli po prawej $stronie$ W rezultacie problem spełnienia ograniczeń można wykorzystać do ustawienia ograniczenia, którego relacją jest tabela po prawej stronie, która może nie być w języku ograniczeń.

W rezultacie, jeśli problem spełnienia ograniczeń ma zbiór rozwiązań w tabeli po lewej stronie, każdą relację można wyrazić, rzutując na odpowiedni zestaw zmiennych. Sposobem na uzyskanie tej tabeli jako zbioru rozwiązań jest umieszczenie każdego możliwego ograniczenia, które nie jest naruszane przez wymagane rozwiązania.

Na przykład, jeśli język zawiera relację binarną reprezentującą dysjunkcję logiczną (relację zawierającą wszystkie krotki dwóch elementów, która zawiera co najmniej 1), relacja ta jest nakładana jako ograniczenie na i b $a$ \ $} displaystyle b}$$} styl wyświetlania (1,0)}$ ponieważ ich wartości w powyższej tabeli to ponownie i ${\ Displaystyle (1,1)}$ , $\ Displaystyle$ . Ponieważ wszystkie te wartości spełniają ograniczenie, zostaje ono umieszczone. Z drugiej strony ograniczenie z tą relacją nie jest nakładane na $,$$)$ ograniczenie powyższej tabeli do tych dwóch zmiennych zawiera $)}$${\ displaystyle (0,0$ jako trzeci wiersz, a ta ocena narusza to ograniczenie.

Uniwersalnym gadżetem porządku $,$ aby uzyskać powyższą tabelę. Rozwiązania uniwersalnego gadżetu obejmują wiersze tej tabeli, ale mogą zawierać inne wiersze. Jeśli rozwiązaniami są dokładnie wiersze tabeli, każdą relację można wyrazić, rzutując na podzbiór zmiennych. Jednak nawet jeśli rozwiązania obejmują inne wiersze, nadal można wyrazić pewne relacje. Cechą uniwersalnego gadżetu jest to, że jest w stanie wyrazić przez projekcję każdą relację, która może być wyrażona przez projekcję z dowolnego problemu spełnienia ograniczeń opartego na tym samym języku. $,$ uniwersalny gadżet porządku $wyraża$ wszystkie relacje wyrazić w języku ograniczeń.

Biorąc pod uwagę określoną relację, jej wyrażalność w języku można sprawdzić, rozważając dowolną listę zmiennych, których kolumny w powyższej tabeli („idealne” rozwiązania uniwersalnego gadżetu) tworzą tę relację. Relację można wyrazić w języku wtedy i tylko wtedy, gdy rozwiązania uniwersalnego gadżetu pokrywają się z relacją rzutowaną na taką listę zmiennych. Innymi słowy, można sprawdzić wyrażalność, wybierając zmienne „tak, jakby” rozwiązania uniwersalnego gadżetu były jak w tabeli, a następnie sprawdzić, czy ograniczenie „rzeczywistych” rozwiązań jest rzeczywiście tożsame z relacją. W powyższym przykładzie wyrażalność relacji w tabeli po prawej stronie można sprawdzić, sprawdzając, czy rozwiązania uniwersalnego gadżetu, ograniczone do zmiennych, są dokładnie ${\ displaystyle b}$ i ${\ displaystyle d}$ wiersze tej tabeli.

Rozwiązania jako funkcje w uniwersalnym gadżecie

Warunek konieczny dla wykonalności można wyrazić w kategoriach uniwersalnego gadżetu. Rozwiązania takiego gadżetu można zestawić w następujący sposób:

abcdefgh --------------- 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 (rozwiązania istniejące z definicji) 1 0 1 0 1 0 1 0 --- ------------ .... 1 0 0 1 1 1 0 0 (możliwe inne rozwiązania) ....

Ten stół składa się z dwóch części. Pierwsza część zawiera rozwiązania, które istnieją z definicji tego problemu; druga część (która może być pusta) zawiera wszystkie pozostałe rozwiązania. Ponieważ kolumny tabeli są z definicji powiązane z możliwymi $krotkami$ wartości dziedziny, każde rozwiązanie można postrzegać jako funkcję od - krotki elementów do pojedynczej ${\ displaystyle k}$ element.

Funkcję odpowiadającą rozwiązaniu można obliczyć na podstawie pierwszej części powyższej tabeli i rozwiązania. Na przykład dla ostatniego rozwiązania zaznaczonego w tabeli $: po pierwsze, te$ tę można wyznaczyć dla argumentów w następujący sposób część wiersza „ " na stole; wartością funkcji jest wartość rozwiązania w tej samej kolumnie, czyli 0.

Warunkiem koniecznym traktowalności jest istnienie rozwiązania uniwersalnego gadżetu pewnego rzędu, który jest częścią pewnych klas funkcji. Ten wynik dotyczy jednak tylko języków zredukowanych, które są zdefiniowane poniżej.

Funkcje zgniatające i domeny zredukowane

Funkcje zgniatania to funkcje używane do zmniejszania rozmiaru domeny języków z ograniczeniami. Funkcja zgniatania jest zdefiniowana w kategoriach podziału domeny i reprezentatywnego elementu dla każdego zestawu w podziale. Funkcja zgniatania odwzorowuje wszystkie elementy zbioru w podziale na reprezentatywny element tego zbioru. Aby taka funkcja była funkcją zgniatającą, konieczne jest również, aby zastosowanie funkcji do wszystkich elementów krotki relacji w języku dało kolejną krotkę w relacji. Zakłada się, że partycja zawiera co najmniej zestaw o rozmiarze większym niż jeden.

$pod$$uwagę partycję$ domeny zawierającą zestaw rozmiarów większych $D$ jest funkcją taką, że dla każdego $} displaystyle x, y}$$y)} s : re → re {\$ w tej samej partycji i dla każdej krotki ${\ Displaystyle \ langle x_ {1}, \ ldots, x_ {n} \ rangle \ in R$ } posiada ${\ Displaystyle \ langle s (x_ {1}), \ ldots, s (x_ {n}) \ rangle \ w R}$ .

W przypadku problemów z ograniczeniami w języku z ograniczeniami ma funkcję zgniatania, dziedzinę można zmniejszyć za pomocą funkcji zgniatania. Rzeczywiście, każdy element w zbiorze w podziale można zastąpić wynikiem zastosowania do niego funkcji zgniatania, ponieważ wynik ten gwarantuje spełnienie przynajmniej wszystkich ograniczeń, które zostały spełnione przez element. W rezultacie wszystkie niereprezentatywne elementy mogą zostać usunięte z języka ograniczeń.

Języki z ograniczeniami, dla których nie istnieje funkcja zgniatania, nazywane są językami zredukowanymi; równoważnie są to języki, w których zastosowano wszystkie redukcje za pomocą funkcji zgniatania.

Warunek konieczny ciągliwości

Warunek konieczny dla wykonalności opartej na uniwersalnym gadżecie jest spełniony dla języków zredukowanych. Taki język jest wykonalny, jeśli uniwersalny gadżet ma rozwiązanie, które postrzegane jako funkcja w sposób określony powyżej jest albo funkcją stałą, funkcją większościową, idempotentną funkcją binarną, funkcją afiniczną lub półprojekcją.

•   Dechter, Rina (2003). Przetwarzanie ograniczeń . Morgana Kaufmanna. ISBN 1-55860-890-7
• Vardi, Mosze Y. (2000). „Satysfakcja z ograniczeń i teoria baz danych: samouczek” . PODS 2000 . s. 76–85.
•   Bułatow, Andriej A. (2006). „Twierdzenie o dychotomii dla problemów spełniania ograniczeń na zbiorze 3-elementowym”. Dziennik ACM . 53 (1): 66–120. doi : 10.1145/1120582.1120584 . S2CID 18220438 .