Ci sono problemi complete per P e NP sotto altri tipi di riduzioni?

Question

So che la classe di complessità $ \ mathsf {P} $ ha problemi completa w.r.t. $ \ Mathsf {CN} $ e $ \ mathsf {} L $ riduzioni.

Sono queste due classi le uniche possibili classi di riduzioni in base al quale $ \ mathsf {P} $ ha problemi completi?

Inoltre, quali classi di riduzione può essere usato per $ \ {mathsf NP} $ accanto a riduzioni in tempo polinomiale?

Answer 1

Le vostre domande contiene alcune frasi scorrette o poco chiari. Nè “classe di complessità X ha riduzione Y” o “possiamo usare riduzione Y per classe di complessità X” ha un senso. In aggiunta, ci sono almeno due definizioni note sotto il nome di “riduzioni polinomiali,” entrambi i quali sono utilizzati per studiare NP-completo: polinomiali riduzioni molti-uno e polinomiali riduzioni Turing. Ma in questa risposta, io ignorare la differenza tra molti-uno riduzioni e le riduzioni di Turing, e mi concentrerò solo sulle restrizioni delle risorse di riduzione, perché altrimenti la risposta diventerà troppo lungo e sfocati.

Ora vi ribadire ciò che si potrebbe desiderare di chiedere, e rispondere a loro.

Ci sono definizioni di riduzioni rispetto alle quali NP-completo può essere definito, esclusi quelli a riduzioni in tempo polinomiale? Ci sono delle definizioni di riduzioni rispetto al quale P-completezza può essere definito, ad eccezione delle riduzioni NC e log-spazio riduzioni?

Come Artem e Raffaello detto, è possibile definire quello che vuoi.

Ci sono delle definizioni di riduzioni effettivamente utilizzato per studiare NP-completezza nella letteratura, diversa da una riduzione polinomiale in tempo? Ci sono delle definizioni di riduzioni in realtà utilizzato per lo studio P-completezza nella letteratura, diversa da riduzioni NC e riduzioni di log-spaziali?

Sì. Ad esempio, utilizza Papadimitriou riduzioni log-spazio tutto suo libro di testo [Pap94], compresa la definizione di NP-completezza. (Nota:. In [Pap94], il termine significa “L-riduzione” qualcosa di completamente diverso dalla riduzione di log-spazio) Per quanto riguarda il P-completezza, Carolina del Nord ^k riduzioni sono di cui [GHMRSS00]. Questo è un caso speciale di riduzioni NC, e più in generale di riduzioni di log-spazio per il k =2.

Ma sono davvero diverse nozioni, o definizioni solo diversi per lo stesso concetto?

Al momento, nessuno lo sa. Ad esempio, log-spazio riducibilità e polinomiale riducibilità sono equivalenti se e solo se L = P.

[GHMRSS00] Raymond Greenlaw, H. James Hoover, Satoru Miyano, Walter L. Ruzzo, Shuji Shiraishi, e Takayoshi borsetta. Il Parallel calcolo del progetto: Volumi I-III , 2000. http: // www. cs.armstrong.edu/greenlaw/research/PARALLEL/

[Pap94] Christos H. Papadimitriou. complessità computazionale . Addison-Wesley, 1994.

Answer 2

Si noti che se la classe di complessità $ C $ ha un problema completo sotto una classe di riduzioni $ A $, quindi lo stesso problema sarà completo per $ C $ sotto e classe di riduzione contenenti $ A $.

In genere prove completezza andare fino in classe molto più debole di riduzioni di solito ha dichiarato (per esempio, con $ \ {mathsf AC ^ 0} $ riduzioni). Ogni classe di riduzioni contenenti $ \ mathsf {AC ^ 0} $ sarebbe sufficiente e ci sono innumerevoli molte di queste classi.

Si consiglia inoltre di controllare il seguente documento:

• Agrawal, M, Allender, E., Impagliazzo, R., Pitassi, T., e Rudich, S., " ridurre la complessità delle Riduzioni ", Journal of Computational Complexity, 10, pp.117-138, 2001. versione preliminare in Proceedings of ACM STOC 2001.

Answer 3

Come note Artem nel suo , la questione è piuttosto insignificante, come si può definire quello che vuoi. Lasciatemi illustrare dove le cose iniziano ad essere "una specie di stupido".

Qualche notazione: Per due problemi $ P, Q $, scrittura $ P \ leq_F Q $ per alcune classi di funzioni $ F $ se c'è $ f \ in F $ tale che $ P (x) = Q (f (x)) $ per tutti gli ingressi $ x $ (di $ P $), cioè se $ P $ può essere $ F $ -Ridotto a $ Q $. Scrivi $ XC_F $ per la classe di $ X $ problemi -Complete rispetto ai $ F $, che è

$ \ qquad \ displaystyle XC_F = \ {P \ in X \ metà \ forall Q \ in X. \ Q \ leq_F P \} $.

Indichiamo inoltre con $ T_X $ l'insieme di (asintoticamente ottimali) funzioni operazionali di algoritmi che funzioni di elaborazione in un insieme $ X $.

Consideriamo ora una classe arbitraria (complessità) dei problemi di $ X $ ¹. Se ci limitiamo spazio riduzione $ F $ in termini di complessità temporale - tutto è possibile qui - ci sono circa due casi:

• $ T_F \ supseteq \ Omega (T_X) $ ² -. Riduzioni non sono più veloce di risolutori di problemi

  In questo caso, $ XC_F = X $ - questo non è chiaramente molto interessante per la teoria della complessità. Considerando ad esempio $ F $ può essere utile nella pratica, soprattutto se $ T_F \ subseteq \ Theta (X) $; è possibile ridurre tutti i problemi in $ X $ ad una manciata di problemi che si possono risolvere molto bene. programmazione lineare e SAT sono esempi tipici causa di risp LP- altamente ottimizzato. SAT-solver.

• $ T_F \ subseteq o (X) $ - riduzioni sono più veloci di risolutori di problemi

  Qui le cose interessanti può accadere, che è di $ XC_F \ subset X $ o $ XC_F \ neq XC_ {F '} $ per diversi spazi di riduzione. Sia che questi fatti hanno ramificazioni interessanti dipende dalla scelta concreta di $ X $ e $ F $. Si noti che $ XC_F = \ emptyset $ potrebbe accadere, che è di per sé abbastanza interessante.

  Cose sicuramente diventato poco interessante quando si sceglie $ F $ così "piccolo" che $ \ leq_F $ è scarsa, che è a pochi riduzioni sono possibili. Pensate a $ X = \ {mathsf NP} $ e $ F $ tale che $ T_F \ subseteq O (n) $; riduzioni devono ridursi di ingresso dimensioni in modo significativo e non può spendere troppo tempo su di esso, in modo da $ F $ non è molto potente.

  Si noti, però, che anche una restrizione a $ T_F \ subseteq O (1) $ foglie relazioni significative; per esempio, "è di $ x $ un intero ancora?" può essere ridotto a "Is $ x $ 's primo bit 0?" a $ O (1) $ tempo e nello spazio. Quindi potrebbe essere interessante studiare anche tali riduzioni deboli per scoprire quali problemi sono vicino alla quale gli altri in termini di complessità riduzione; è sicuramente vedere tali differenze di $ classico \ mathsf {NPC} = \ mathsf {} NP C_P $ riduzioni.

Tecnicamente, c'è un terzo caso, ad esempio $ T_F = P $ e $ T_X = \ Theta (n ^ 3) $; in questo caso - se $ F $ è abbastanza ricco - si applicano i commenti sul caso uno. Si noti inoltre che la questione qual caso $ F $ cade può essere interessante in sé: "$ \ mathsf {P = NP} $?" chiede in sostanza se $ T_F = \ Theta (X) $ (e anche se $ F = \ Theta (XC_F) $).

---

1. Per essere una "corretta" classe di complessità, deve essere una sorta di w.r.t. "verso il basso chiuso" complessità.
2. $ \ circ (X) $ per una classe funzione di $ X $ e $ \ circ $ simbolo di Landau è la naturale estensione dei soliti simboli di Landau, vale a dire $ \ circ (X) = \ bigcup_ {f \ in X } \ circ (f) $.