zdaniowe systemy dowodzenia i odpowiadające im ograniczone teorie arytmetyczne
To pytanie jest inspirowane podobnym pytaniem o matematykę stosowaną w matematycznym przepływie i ta dokuczliwa myśl, że ważne pytania TCS, takie jak P vs. NP, mogą być niezależne od ZFC (lub innych systemów). Jako małe tło, matematyka odwrotna to projekt znalezienia aksjomatów niezbędnych do...
To naiwne pytanie z mojej wiedzy; z góry przeprasza. Hipoteza Goldbacha i wiele innych nierozwiązanych pytań w matematyce można zapisać jako krótkie formuły w rachunku predykatów. Na przykład artykuł Cooka „Czy komputery mogą rutynowo odkrywać dowody matematyczne?” formułuje tę hipotezę jako ∀ n...
Pytanie dotyczące teorii „ Co to jest NP ograniczony do świadków wielkości liniowej? ” Dotyczy klasy NP ograniczonej do świadków wielkości liniowej , aleO ( n )O(n)O(n) Czy istnieją naturalne problemy NP-zupełne, w których (tak) przypadki wielkości wymagają świadków o rozmiarze większym niż n...
W solverach SAT często można znaleźć metody płaszczyzny cięcia, zmienną propagację, odgałęzienie i wiązanie, uczenie się klauzul, inteligentne cofanie, a nawet ręcznie tkaną ludzką heurystykę. Jednak przez dziesięciolecia najlepsze solwery SAT polegały w dużej mierze na technikach sprawdzania...
Ostatnio widziałem kilka artykułów na temat arxiv, które odnoszą się do systemu sprawdzania zwanego sumą kwadratów. Czy ktoś może wyjaśnić, co to jest dowód sumy kwadratów i dlaczego takie dowody są ważne / interesujące? Jak są one powiązane z innymi algebraicznymi systemami dowodowymi? Czy są...
Czy istnieje przegląd algorytmów obliczania interpolantów? Co z artykułami na temat tylko jednego algorytmu? Najbardziej interesuje mnie przypadek i C = q plus ograniczenie, że interpolant jest tak mały, jak to możliwe. (Znam pracę McMillana z 2005 roku , która opisuje, jak uzyskać interpolanty,...
XORification to technika utrudniania funkcji lub formuły boolowskiej poprzez zastąpienie każdej zmiennej XOR k ≥ 2 odrębnych zmiennych x 1 ⊕ … ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Zdaję sobie sprawę z zastosowania tej techniki w złożoności dowodu, głównie w celu...
Szukam naturalnych przykładów wydajnych algorytmów (tj. W czasie wielomianowym) ul ich poprawność i skuteczność można konstruktywnie udowodnić (np. w lub ), alePRAPRAPRAHAHAHA nie jest znany żaden dowód wykorzystujący tylko wydajne koncepcje (tzn. nie wiemy, jak udowodnić ich poprawność i...
Czytając artykuł „ Teoria aplikacyjna dla FPH ”, można natknąć się na następujący fragment: Biorąc pod uwagę teorie charakteryzujące klasy złożoności obliczeniowej, istnieją trzy różne podejścia: w jednym funkcje, które można zdefiniować w teorii, są „automatycznie” w ramach pewnej klasy...
Wiemy, że DPLL oparte SAT-rozwiązują nie odpowie poprawnie na unsatisfiable wystąpień (zasada dziura gołąb), np na „nie jest injective mapowanie od n + 1 do n ”:P H PP.H.P.\mathrm{PHP}n + 1n+1n+1nnn P H Pn + 1n: = ⎛⎝⋀i ∈ [ n + 1 ] ⋁j ∈ [ n ] pja , j⎞⎠∧ ⎛⎝⋀I ≠ ja′∈ [ n + 1 ] ⋀j ∈ [ n ] ( ¬ pja , j∨...
To pytanie dotyczy logiki zdań i wszystkie wystąpienia „rozstrzygania” należy interpretować jako „rozstrzyganie zdań”. To pytanie jest bardzo proste, ale od dłuższego czasu mnie niepokoi. Widzę, że ludzie twierdzą, że rozwiązanie zdań jest kompletne, ale widzę też, że ludzie twierdzą, że...
Czy byłyby jakieś poważne konsekwencje, gdyby SAT miał co najwyżej podwykładnicze dowody niesatysfakcjonujące, a jeszcze silniej, SAT miałby algorytmy podwykładniczego
Zakładając, że NP! = CoNP, to nie ma certyfikatu wielomianu dla problemu pełnego coNP. Ale co z podwykładniczym certyfikatem wielkości? Czy w szczególności w przypadku coSAT istnieje podwykładniczy dowód wielkości, aby udowodnić, że formuła jest niezadowalająca? Jeśli nie, jakie są negatywne...
Przypomnijmy, że szerokość o rozdzielczości odrzucenia o wzorze CNF jest maksymalna liczba literałach w klauzuli występującego w . Dla każdego istnieją niezadowalające wzory w 3-CNF st. Każde odrzucenie rozdzielczości wymaga szerokości co najmniej .F.RRRfaFFw F F wRRRwwwfaFFfaFFwww Potrzebuję...
Niedawno zacząłem dużo czytać o złożoności dowodów i bardzo podobało mi się to, co czytałem. Naprawdę chciałbym dowiedzieć się więcej na ten temat, ale mam trudności ze znalezieniem dobrego materiału dla początkujących. Czy ktoś mógłby polecić jakieś
Załóżmy, że NP = co-NP i wielomian ogranicza długość dowodu niezadowolenia dla instancji 3-CNF . Czy są więc jakieś wyniki w jakiej formie może przyjąć jakiś dowód niezadowolenia dla długości ? Tzn. Ogólnie, czy taki dowód musiałby na przykład wykorzystać pełną moc logiki drugiego rzędu nad...
Motywacją tego pytania jest fakt, że większość ciągów n-bitowych jest nieściśliwa. Intuicyjnie możemy zaproponować przez analogię, że większość dowodów dla tautologii jest nieściśliwa dla wielkości wielomianowej. Zasadniczo, moja intuicja jest taka, że niektóre dowody są z natury losowe i nie...
Rozwiązanie to program mający na celu wykazanie niezadowalającej wartości CNF. Dowodem na rozwiązanie jest logiczne odjęcie pustej klauzuli dla klauzul początkowych w CNF. W szczególności każdy punkt początkowy można wywnioskować, i dwóch punktach ∨ x i B ∨ Kontakty x klauzula ∨ B można...
W przemówieniu Razborowa opublikowano dziwne oświadczenie. Jeśli FACTORING jest trudny, to małe twierdzenie Fermata nie jest możliwe do udowodnienia w S12S21S_{2}^{1} . Co to jest S12S21S_{2}^{1} i dlaczego aktualnych dowodów nie ma w S12S21S_{2}^{1} ?
Czy istnieje naturalna klasa formuł CNF - najlepiej taka, która była wcześniej badana w literaturze - o następujących właściwościach:doCC jest łatwym przypadkiem SAT, takim jak np. Horn lub 2-CNF, tj. Członkostwo w C można badać w czasie wielomianowym, a wzory F ∈ C można badać pod kątem...