Pytania otagowane jako lo.logic

Logika obliczeniowa i matematyczna.

1
FO-uniform AC0 z pewnym orzeczeniem
Moje pytanie dotyczy teorii modeli skończonych / złożoności opisowej, więc FO(R)FO(R)FO(R) będzie oznaczać „pierwszy rząd nad skończonymi słowami binarnymi, przy użyciu predykatów Rs i jednoargumentowego predykatu P true na pozycji 1 w słowie”. Chciałbym wiedzieć, czy jest jakakolwiek caracterization FO(&lt;,R)FO(&lt;,R)FO(<,R) z R dowolnym orzeczeniem NrNr\mathbb N^rdla jakiegoś r? Na przykład …
1
Funkcjonalna kompletność 3-wartościowej logiki
W kontekście niektórych ostatnich prac zdefiniowaliśmy język oparty na trójwartościowej logice à la Kleene, gdzie111 oznacza prawdę, 000 za fałsz i ⊥⊥\botza błąd lub nie wiem. Aby pokazać, że nasz język jest ekspresyjny, chcieliśmy udowodnić, że możemy zbudować zestaw funkcjonalnie kompletnych operatorów. Trudno było znaleźć istniejące wyniki w literaturze. Znaleźliśmy …
2
Czy dobre PCP dla NP dają nam dobre PCP dla całej hierarchii wielomianowej?
Twierdzenie PCP stwierdza, że ​​każdy problem decyzyjny w NP ma probabilistycznie sprawdzalne dowody (lub równoważnie, że istnieje kompletny i quasi-dźwiękowy system dla twierdzeń w NP wykorzystujący stałą złożoność zapytań i logarytmicznie wiele losowych bitów). „Mądrość ludowa” otaczająca twierdzenie PCP (ignorując przez chwilę znaczenie PCP dla teorii przybliżenia) polega na tym, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.