Tło :
W oryginalnym dokumencie UGC Subhash Khota ( PDF ) udowadnia trudność UG w podejmowaniu decyzji, czy dana instancja CSP z ograniczeniami w całej formie Niezupełna (a, b, c) w stosunku do trójskładnikowego alfabetu przyznaje zadanie spełniające 1 - ograniczeń lub czy nie ma zadowalających zadań 8ograniczeń, dla dowolnie małychϵ>0.
Jestem ciekaw, czy wynik ten został uogólniony dla dowolnej kombinacji -ary ograniczeń dla £ -l ≥ 3 i domen zmiennych wielkości k ≥ 3 , gdzie £ -l ≠ k ≠ 3 . To jest,
Pytanie :
Czy znana jest twardość wyników aproksymacji dla predykatu dla x i ∈ G F ( k ) dla ℓ , k ≥ 3 i ℓ ≠ k ≠ 3 ?
Szczególnie interesuje mnie kombinacja wartości ; np. predykat Nie równe ( x 1 , … , x k ) dla x 1 … , x k ∈ G F ( k ) .