Stwierdzenia implikujące

22

To jest pytanie otwarte, za co z góry przepraszam.

Czy istnieją przykłady zdań, które (pozornie) nie mają nic wspólnego ze złożonością lub maszynami Turinga, ale odpowiedź na które sugerowałaby ? $\mathbf{P}\neq \mathbf{NP}$

cc.complexity-theory complexity-classes p-vs-np Dominic van der Zypen
źródło

4

Czy „Nie ma systemu dowodowego dla logiki zdań, w którym każda tautologia ma dowód wielomianowej (długości ) długości”. liczyć, czy jest to zbyt bliskie złożoności ze względu na wielomian?

φ

$\varphi$

φ

$\varphi$

Jan Johannsen,

Ponieważ nie ma „dokładnych” odpowiedzi na moje pytanie, twoje przypuszczenie by się liczyło ... Po prostu szukam zaskakujących i różnych punktów widzenia na problem P vs NP

Dominic van der Zypen,

4

Wydaje mi się, że złożoność opisowa podaje kilka przykładów. Na przykład stwierdzenie „istnieją właściwości (uporządkowanych struktur) możliwe do wyrażenia za pomocą formuł egzystencjalnych drugiego rzędu, które nie mogą być wyrażone za pomocą uniwersalnych wzorów drugiego rzędu” jest równoważne z odpowiedzią @ JanJohannsen, natomiast „istnieją właściwości (uporządkowanych struktur) wyrażone przez formuły egzystencjalne drugiego rzędu, których nie można wyrazić formułami pierwszego rzędu z operatorem najmniej ustalonego punktu ”, to dokładnie . Czy to się liczy?

P \neq N P

$\mathsf P\neq\mathsf{NP}$

Damiano Mazza

„ i ” * rimshot *

N \neq 1

$\mathbf{N}\neq 1$

P \neq 0

$\mathbf{P}\neq 0$

David Richerby

1

Podobne pytanie cstheory.stackexchange.com/questions/9806/...

Tayfun Pay

14

System dowodowy dla logiki zdań jest nazywany ograniczeniem wielomianowym , jeśli każda tautologia $\varphi$ ma dowód w systemie długości wielomianu o długości $\varphi$ .

Stwierdzenie „Nie ma wielomianowo ograniczony zdaniową systemu kontrolnego” jest równoznaczne z przez klasyczne wyniku Cook i Reckhow , więc implikuje . $\mathsf{NP} \neq \mathsf{co}\text-\mathsf{NP}$ $\mathsf{P} \neq \mathsf{NP}$

Jan Johannsen
źródło

2

Sądzę, że (zgodnie z definicją systemu dowodu zdań dla kompletnego języka tautologii

) założenie („Nie ma systemu dowodu dla logiki zdań, w którym każda tautologia

ma dowód wielomianu (w długość

) długość ”) jest prawie identyczna z przyjęciem

; a zatem niemal identyczny zakładając

.

c o N P

$\mathsf{coNP}$

φ

$\varphi$

φ

$\varphi$

N P \neq c o N P

$\mathsf{NP}\neq\mathsf{coNP}$

N P \neq P

$\mathsf{NP}\neq\mathsf{P}$

Iddo Tzameret,

@IddoTzameret: ale musimy wiedzieć, że jest tautologią

-Complete, prawda? I to nie jest trywialne. Wydaje mi się, że ten przykład potwierdza zainteresowanie „naturalnymi” pełnymi problemami: możemy mówić o klasach złożoności bez wyraźnego mówienia o maszynach używanych do ich definiowania (co wydaje się być tym, o co prosi OP). A może źle zrozumiałem twój komentarz ...

c o N P

$\mathsf{coNP}$

Damiano Mazza

@Damiano, myślę, że fakt, że TAUT jest kompletny coNP, jest trywialny, w tym sensie, że wynika z jego definicji i kompletności NP dla SAT.

Iddo Tzameret,

@IddoTzameret, OK, ale trzeba zgodzić się, że

-completeness z SAT nie jest trywialne, prawda? Właśnie to mówiłem. Chodzi mi o to, że między stwierdzeniem „

” sformułowanym w odniesieniu do maszyn Turinga i ich czasu działania a ciągiem „nie ma wielomianowo ograniczonego systemu dowodu propozycyjnego”. Widzę nietrywialną lukę, zdecydowanie nie „ wygląda „prawie identycznie”. Ta luka jest w kompletności TAUT lub SAT, w zależności od tego, co chcesz, ale tam jest. Nie zgadzasz się

N P

$\mathsf{NP}$

N P \neq c o N P

$\mathsf{NP}\neq\mathsf{coNP}$

Damiano Mazza

1

Tak, właściwość „

jest dowodem

” musi być możliwa do sprawdzenia w czasie wielomianowym (w

i

). I musi być solidny i kompletny, tj. Formuła powinna mieć dowód, że jest to tautologia.

p

$p$

φ

$\varphi$

| p |

$|p|$

| φ |

$|\varphi|$

Jan Johannsen

12

Teoria złożoności geometrycznej (GCT) (także [1]) nie została jeszcze wspomniana. jest to duży ambitny program do łączenia P vs NP z geometrią algebraiczną. np. krótkie streszczenie z badania Zrozumienie podejścia Mulmuley-Sohoni do P vs. NP , Regan:

Stabilność jest nieformalnie pojęciem, że nie jest „chaotyczna” i rozwinęła się w główną gałąź geometrii algebraicznej pod przewodnim wpływem DA Mumforda, między innymi. Ketan Mulmuley i Milind Sohoni [MS02] zauważają, że wiele pytań dotyczących klas złożoności można przerzucić na pytania dotyczące charakteru działań grupowych na niektórych wektorach w pewnych przestrzeniach, które kodują problemy w tych klasach. Ta ankieta wyjaśnia ich ramy z laickiego punktu widzenia i próbuje ocenić, czy to podejście naprawdę dodaje nowej mocy atakom na pytanie P. vs. NP.

także streszczenie w sekcji „Nowa nadzieja?” w Status of the P vs NP problem , Fortnow (2009)

Mulmuley i Sohoni zredukowali pytanie o nieistnienie algorytmów wielomianowych dla wszystkich problemów NP-zupełnych do pytania o istnienie algorytmu wielomianowego (z pewnymi właściwościami) dla konkretnego problemu. To powinno dać nam nadzieję, nawet w obliczu problemów (1) - (3).

Niemniej jednak Mulmuley uważa, że realizacja tego programu zajmie około 100 lat, jeśli w ogóle zadziała.

[1] Wyjaśnienie w stylu Wikipedii teorii złożoności geometrycznej (tcs.se)

vzn
źródło

Dzięki za wprowadzenie GCT! Wydaje się, że dotyka mojego własnego problemu [M], ale wcześniej go nie spotkałem. „Te problemy obliczeniowe można scharakteryzować za pomocą ich symetrii. Program ma na celu wykorzystanie tych symetrii do udowodnienia dolnych granic”.

DukeZhou,

10

Poniższy wynik Raz (Elusive Functions and Lower Bounds for Arithmetic Circuits, STOC'08) jest skierowany na (a nie bezpośrednio ), ale może być wystarczająco blisko dla OP: $VP\neq VNP$ $P\neq NP$

Mapowanie wielomianowe jest -elusywne, jeśli dla każdego mapowania wielomianowego stopnia , Obraz ( ) Obraz ( ). $f:\mathbb F^n \to \mathbb F^m$ $(s, r)$ $Γ : \mathbb F^s → \mathbb F^m$ $r$ $f$ $\not⊂$ $Γ$

Dla wielu ustawień parametrów , jawne konstrukcje nieuchwytnych mapowań wielomianowych implikują silne (aż wykładnicze) dolne granice dla ogólnych obwodów arytmetycznych. $n, m, s, r$

Iddo Tzameret
źródło

Co to jest mapowanie wielomianowe? Masz na myśli „wielomian”? Masz na myśli „funkcję obliczalną w czasie wielomianowym”? Coś innego?

DW

2

Jest to po prostu sekwencja wielomianów , każda z tymi samymi zmiennymi; stąd definiuje mapowanie z na .

m

$m$

n

$n$

F^{n}

$\mathbb{F}^n$

F^{m}

$\mathbb{F}^m$

Iddo Tzameret,

9

istnieje nieco boczna / ostatnio badana dziedzina złożoności zwana złożonością grafów, która bada, w jaki sposób większe wykresy są budowane z mniejszych grafów za pomocą operacji AND i OR krawędzi. Jukna ma niezłą ankietę . w szczególności przy użyciu jednostek „wykresów gwiezdnych” istnieje kluczowe twierdzenie, patrz uwaga p20 1.18 (twierdzenie jest technicznie silniejsze niż poniżej i faktycznie implikuje ): $P \ne NP/poly$

Wiemy już (Twierdzenie 1.7), że istnieją dwustronne wykresy G o złożoności ; w rzeczywistości są to prawie wszystkie wykresy. Z drugiej strony, lemat silnego powiększenia implikuje, że nawet dolna granica dla arbitralnie małej stałej na złożoności gwiazdy wyraźnego grafu przy miałby wielkie konsekwencje w złożoności obwodu: taki wykres dałby wyraźną funkcję boolowską wymagającą obwodu wykładniczego (w liczbie $n × m$ $Star(G) = (nm/ \log n)$ $Star(G) ≥ (2+c)n$ $c > 0$ $n×m$ $G$ $m = o(n)$ $f_G$ $\log_2 nm$ wielkości) rozmiar! (Przypomnijmy, że w przypadku funkcji boolowskich nawet superliniowe dolne granice nie są do tej pory znane). W szczególności, jeśli wykres jest taki, że sąsiedztwo wierzchołków w może być określone przez niedeterministyczną maszynę Turinga działającą w czasie wielomianowym w długość binarna kodów wierzchołków, a następnie dolna granica dla arbitralnie małej stałej oznaczałoby, że . Tak więc złożoność grafów gwiazd odzwierciedla jeden z najbardziej podstawowych problemów informatyki. $G$ $G$ $log_2 n$ $Star(G) ≥ (2 + c)n$ $c > 0$ $P \ne NP$

vzn
źródło

6

Myślę, że masz na myśli . Oświadczenie już powszechnie znane.

P / p o l y ⊅ N P

$P/poly \not \supset NP$

P \neq N P / p o l y

$P \neq NP/poly$

Yonatan N

@YonatanN jest prawdą?

P \neq N P / p o l y

$P\neq NP/poly$

T ....

Tak. Wiadomo, że nawet P / poli zawiera problemy poza P, takie jak problem pojedynczego zatrzymania.

Yonatan N,

Dzięki za link Jukna! „Złożoność jest jednym z kluczowych zjawisk naukowych naszych czasów. W tym rozdziale rozważamy złożoność wykresów”.

DukeZhou,

1

Co powiesz na Philipa Maymina

„ Rynki są efektywne tylko wtedy, gdy twierdzą, że P = NP ”?

RB
źródło

3

Twierdzenia i „dowody” w tym dokumencie nie wyglądają na rygorystyczne, a argumenty wydają mi się brakujące. Czytałeś ten artykuł?

Rahul Savani

Omówiłem to i zgadzam się, że metodologia nie jest aż tak przekonująca, dlatego nazwałem ją „twierdzeniem”, a nie rezultatem.

RB

5

I jest napisane w Microsoft Word: /

gigabajty

0

Funkcja analogi i ; i byłyby również interesujące w badaniu pytania (?). Podczas gdy i są problemami decyzyjnymi, które zwracają bit odpowiedzi tak / nie, i faktycznie zwracają odpowiedzi ( weryfikuje odpowiedzi). Wiemy, że , iff . $P$ $NP$ $FP$ $FNP$ $P$ $=$ $NP$ $P$ $NP$ $1$ $FP$ $FNP$ $FNP$ $FP$ $=$ $FNP$ $P$ $=$ $NP$

użytkownik3483902
źródło

Stwierdzenia implikujące

Odpowiedzi: