Controlla la mia prova che Co-NP!= P

Question

Questo è il lavoro di livello di hobby, non il mio lavoro. Ho scritto questo estratto per condividere alcune idee sulla CO-NP.

L'idea è quella di scegliere una categoria problema in Co-NP, dove la risposta corretta è difficile da verificare a causa della complessità del circuito, esprimerla come formula 1-in-k satellita, e mostrare anche un certificato corto, di cui esiste anche un certificato breve La lunghezza in bit è esattamente il doppio del numero di clausole. Potrebbe essere vero o falso che tutti i problemi di Co-NP hanno un certificato così breve in questo modulo (Co-NP?= NP), ma mostro che indipendentemente da ciò, il Breve certificato per questo problema può essere reso arbitrariamente difficile Trova, a causa della relazione interleavata con NP. Fondamentalmente, voglio evidenziare una particolare dipendenza circolare tra gli oracoli di NP e Co-NP. L'argomento per lo stomp contro il Co-NP= P è che nessun TM può sperare di attaccare il problema della ricerca del certificato breve in tempo sufficiente, poiché il modo in cui definisco il problema ne fa contenere una quantità arbitraria di "Rosso reale". Fondamentalmente, è una ricetta specifica per costruire un problema di co-NP "mostro" da un semplice certificato.

Ora ho molte domande per chiunque abbia una formazione più formale di me:

.
• ha questa categoria di problema è stata espressa con un nome diverso?
• è un ovvio vicolo cieco o inesplorato?
• Come posso esprimere le stesse idee ma più formalmente contro le funzionalità TM?

Answer 1

WTLU è in P.

Algoritmo:

.
• Rendi la monotona della formula 1-in-k satellitare aggiungendo una clausola per ogni coppia di letterali (x + ~ x)= 1 e sostituzione ~ x con una nuova variabile.
• scegli un grande PRIME P, almeno più grande del numero di clausole.
• Trasforma la formula sat 1-in-k in un sistema di equazioni lineari Modulo p.Ogni clausola originale nel modulo (x, y, z ...)= 1 diventa un'equazione (x, y, z ...)= 1 mod p.
• esegue l'eliminazione gaussiana.
• Se la formula è stata un'istanza WTLU, viene trovata una contraddizione prima che viene raggiunta la forma di Echelon di fila, sotto forma di un'equazione contraddittorale 0= k mod P (con k!= 0).

Perché funziona:

Se ci sono due serie di clausole che coprono lo stesso set di letterali, tale che (C1 + c2 + c3 ...)= x e (c1 '+ c2' + c3 '...)= y e x!= Y, allora è anche il caso Modulo p.Pertanto, il sistema di equazioni Modulo P non è neanche soddisfatto.

Answer 2

Ecco un contrargomento. Una struttura di prova simile, potrebbe essere facilmente utilizzata per dimostrare che XOR-SAT è difficile.

.

1. Prendi una formula XOR-SAT insoddisfacente con un grande spazio. Non puoi risolverlo con un algoritmo di risoluzione-simile.

2. Ora esiste un breve certificato di insoddisfabilità, perché Xor-SAT è in P.

3. Se non si conosce l'eliminazione, allora combini clausole casuali insieme fino a quando due clausole hanno le stesse variabili, una riga equivale a zero e l'altra riga è uguale a uno. Il rivestimento è un caso speciale di aggiunta in cui le clausole non hanno letterali in comune.

4. Aggiungi clausole casuali e variabili alla formula XOR-SAT per renderlo più difficile per fare casualmente le cose.

Ma in realtà è possibile effettuare un'eliminazione gaussiana in una quantità polinomiale di tempo e spazio fino a quando due righe si annullano a vicenda a produrre 0= 1.

Per espandere la tua argomentazione e renderlo interessante, dovresti almeno mostrare che esiste una differenza fondamentale con XOR-SAT, per un inizio che non c'è alcun processo simile all'eliminazione in cui è possibile estrarre le variabili uno per uno Durante il processo di isolamento dei 2 serie conflittuali di clausole ignorando le informazioni extra.