Pytania otagowane jako proof-complexity

zdaniowe systemy dowodzenia i odpowiadające im ograniczone teorie arytmetyczne

2
Aksjomaty niezbędne w informatyce teoretycznej
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 udowodnienia pewnych ważnych twierdzeń. Innymi słowy, …
2
Jeśli P = NP, czy moglibyśmy uzyskać dowody hipotezy Goldbacha itp.?
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 [ ( n > 2 ∧ 2 …
6
Naturalne problemy NP-zupełne z „dużymi” świadkami
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 ?nnnnnn Oczywiście możemy budować sztuczne problemy, …
6
Dobrze znane klasy wzorów boolowskich, które wymagają wykładniczo długich prób rozdzielczości
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 rozdzielczości i używają kombinacji innych rzeczy po prostu do pomocy i do …
3
Jakie algorytmy są znane z obliczania interpolantów Craiga?
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, unikając kwantyfikatorów.)A=¬p∧qA=¬p∧qA=\lnot p\land qC=qC=qC=q Tło: Interpolacja …
2
Zastosowania XORification
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 uzyskania niższych granic przestrzeni dla …
3
Konstruktywnie wydajne algorytmy bez sprawdzania poprawności i wydajności
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 wydajność w lub ).TV0TV0TV^0S12S21S^1_2 Mogę samodzielnie tworzyć sztuczne przykłady. Chcę jednak …
2
Czy rozstrzyganie propozycji jest kompletnym systemem dowodowym?
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 rozwiązanie jest niepełne. Rozumiem sens niepełnej rozdzielczości. Rozumiem również, …
3
Teorie charakteryzujące klasy złożoności obliczeniowej
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 złożoności. Na takim koncie należy ograniczyć składnię, aby zagwarantować, że …
1
Formuła 3-CNF, która wymaga szerokości rozdzielczości
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ę konkretnego przykładu niezadowalającej formuły w 3-CNF (tak małej i prostej, jak to …
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.