Polynomisk kreativitet

I beräkningskomplexitetsteori är polynomkreativitet en teori som är analog med teorin om kreativa uppsättningar i rekursionsteori och matematisk logik . K $k$ - kreativa uppsättningar är en familj av formella språk i komplexitetsklassen NP komplement bevisligen inte har $O(n^{k})$ -tids icke-deterministiska igenkänningsalgoritmer. Det anses allmänt att NP är ojämlikt med co-NP (klassen av komplement av språk i NP), vilket skulle antyda starkare att komplementen till alla NP-kompletta språk inte har polynom-tid icke-deterministiska igenkänningsalgoritmer. Men för $k$ -kreativa uppsättningarna kan avsaknaden av en (mer begränsad) igenkänningsalgoritm bevisas, medan ett bevis på att NP ≠ co-NP förblir svårfångade.

De $k$ -kreativa uppsättningarna antas utgöra motexempel till Berman-Hartmanis-förmodan om isomorfism av NP-kompletta uppsättningar. Det är NP-komplett att testa om en indatasträng tillhör något av dessa språk, men inga polynomiska tidsisomorfismer mellan alla sådana språk och andra NP-kompletta språk är kända. Polynomkreativitet och $k$ -kreativa uppsättningar introducerades 1985 av Deborah Joseph och Paul Young, efter tidigare försök att definiera polynomanaloger för kreativa uppsättningar av Ko och Moore.

Definition

Intuitivt är en uppsättning kreativ när det finns en polynom-tidsalgoritm som skapar ett motexempel för vilken som helst kandidat för snabb icke-deterministisk igenkänningsalgoritm för dess komplement.

Klasserna av snabba icke-deterministiska igenkänningsalgoritmer formaliseras av Joseph och Young som mängderna $\mathrm {NP} ^{(k)}$ av icke-deterministiska Turing-maskinprogram p $\displaystyle p}$ som, för ingångar $x$ som de accepterar, har en accepterande sökväg med ett antal steg som är högst $|p|(|x|^{k}+1)$ . Denna notation bör särskiljas med den för komplexitetsklassen NP. Komplexitetsklassen NP är en uppsättning formella språk, medan $\mathrm {NP} ^{(k)}$ istället är en uppsättning program som accepterar några av dessa språk. Varje språk i NP känns igen av ett program i en av uppsättningarna $\mathrm {NP} ^{(k)}$ , med en parameter $k$ som är (upp till faktor $|p|$ i gränsen för antalet steg) exponenten i polynomets gångtid för programmet .

Enligt Joseph och Youngs teori är ett språk $L$ i NP $k$ -kreativt om det är möjligt att hitta ett vittne som visar att komplementet till $L$ inte känns igen av någon program i $\mathrm {NP} ^{(k)}$ . Mer formellt borde det finnas en polynomiskt beräkningsbar funktion $f$ som mappar program i denna klass till ingångar där de misslyckas. När det ges ett icke-deterministiskt program $p$ i $\mathrm {NP} ^{(k)}$ , bör funktionen $f$ producera en inmatningssträng $x=f(p)$ som antingen tillhör $L$ och får programmet att acceptera ${\displaystyle x} ,$ eller inte tillhör $L$ och orsakar programmet för att avvisa $x$ . Funktionen $f$ kallas en produktiv funktion för $L$ . Om denna produktiva funktion finns, producerar inte det givna programmet det beteende på ingången $x$ som skulle förväntas av ett program för att känna igen komplementet till $L$ .

Existens

Joseph och Young definierar en polynomtidsfunktion $f$ för att vara polynomiellt ärlig om dess körtid som mest är en polynomfunktion av dess utdatalängd. Detta tillåter till exempel funktioner som tar polynomtid men producerar utdata med mindre än polynomlängd. Som de visar är varje en-till-en polynomiellt ärlig funktion $f$ den produktiva funktionen för ett $k$ -kreativt språk $K_{f}^{k}$ .

Givet $f$ , definierar Joseph och Young ${\textstyle K_{f}^{k}}$ som uppsättningen av värden $f(p)$ för icke-deterministiska program ${ \displaystyle p}$ som har en accepterande sökväg för $f(p)$ med högst ${\textstyle |p|(|f(p)|^{k}+1)}$ steg. Detta antal steg (på den ingången) skulle stämma överens med $p$ som ${\textstyle \mathrm {NP} ^{(k)}}$ . tillhör Då hör $K_{f}^{k}$ till NP, för givet en ingång $f(p)$ kan man icke-deterministiskt gissa både $p$ och dess accepterande sökväg och verifiera sedan att indata är lika med $f(p)$ och att sökvägen är giltig för $p$ .

Språk ${\textstyle K_{f}^{k}}$ är $k$ -kreativ, med $f$ som sin produktiva funktion, eftersom varje program $p$ i $\mathrm {NP} ^{(k)}$ mappas av $f$ till ett värde $f(p)$ som antingen accepteras av ${\ displaystyle p}$ (och tillhör därför även $K_{f}^{k}$ ) eller avvisas av ${\displaystyle p} (och$ tillhör $K_{ f}^{k}$ ). därför inte heller

Fullständighet

Varje $k$ -kreativ uppsättning med en polynomiellt ärlig produktiv funktion är NP-komplett. För alla andra språk $X$ i NP, enligt definitionen av NP, kan man översätta vilken indata ${\displaystyle x} som helst$ för $X$ till ett icke-deterministiskt program $p_{x}$ som ignorerar sin egen inmatning och istället söker efter ett vittne för ${\displaystyle x} ,$ accepterar dess input om den hittar en och avvisar något annat. Längden på $p_{x}$ är polynom i storleken $x$ och ett utfyllnadsargument kan användas för att göra $p_{x}$ tillräckligt lång (men fortfarande polynom ) för dess körtid för att kvalificera sig för medlemskap i $\mathrm {NP} ^{(k)}$ . Låt $f$ vara den produktiva funktionen som används för att definiera en given $k$ -kreativ uppsättning ${\displaystyle L} ,$ och låt $g$ vara översättningen från $x$ till $p_{x}$ . Sedan mappar sammansättningen av $g$ med $f$ ingångar av $X$ till motexempel för algoritmerna som testar dessa indata. Den här kompositionen mappar indata som tillhör $X$ till strängar som tillhör L $\displaystyle L}$ { och ingångar som inte tillhör $X$ till strängar som inte tillhör L $\displaystyle$ . Det är alltså en polynom-tid många-en-reduktion från $X$ till $L$ . Eftersom $L$ är (per definition) i NP, och alla andra språk i NP har en reduktion till det, måste det vara NP-komplett.

Det är också möjligt att starkare bevisa att det finns en inverterbar sparsam reduktion till $k$ -kreativ uppsättning.

Tillämpning på Berman-Hartmanis-förmodan

Berman-Hartmanis-förmodan säger att det existerar en polynom-tidsisomorfism mellan två NP-kompletta uppsättningar: en funktion som mappar ja-instanser av en sådan mängd en-till-en till ja-instanser av den andra, tar polynomtid, och vars inversa funktion också kan beräknas i polynomtid. Den formulerades av Leonard C. Berman och Juris Hartmanis 1977, baserat på observationen att alla NP-kompletta uppsättningar som var kända vid den tiden var isomorfa. En likvärdig formulering av gissningen är att varje NP-komplett set är paddable . Detta betyder att det finns en polynom-tid och polynom-tid-inverterbar en-till-en-transformation $h(x,y)$ från yes-instanser $x$ till större yes -instanser som kodar den "irrelevanta" informationen $y$ .

Det är dock okänt hur man hittar en sådan utfyllnadstransformation för ett $k$ -kreativt språk vars produktiva funktion inte är polynom-tidsinverterbar. Därför, om envägspermutationer existerar, ger de $k$ -kreativa språken som har dessa permutationer som sina produktiva funktioner kandidatmotexempel till Berman-Hartmanis- förmodan.

Den (obevisade) Joseph–Young gissningen formaliserar detta resonemang. Gissningen säger att det finns en enkelriktad längdökande funktion $f$ så att $K_{f}^{k}$ inte är paddbar. Alan Selman observerade att detta skulle innebära en enklare gissning, den krypterade kompletta uppsättningens gissning : det finns en envägsfunktion $f$ så att $\mathrm {SAT}$ (uppsättningen av ja- instanser för tillfredsställbarhetsproblemet ) och $f(\mathrm {SAT} )$ är -isomorfa Det finns ett orakel i förhållande till vilket envägsfunktioner existerar, båda dessa gissningar är falska, och Berman-Hartmanis-förmodan är sann.