Existem generalizações naturais de P versus NP?

Resposta Aceita

A resposta de Scott Aaronson foi "aceita" (principalmente porque é a única resposta!)

Resumo de uma frase da resposta As   generalizações plausivelmente naturais da questão P versus NP não são obviamente mais fáceis de resolver do que P versus NP em si.

Uma obstrução a uma resposta geral   A pergunta original supunha que toda classe de complexidade A se associa "naturalmente" a uma NA de generalização não determinística - no entanto, uma classe de complexidade geral A pode ser definida de tantas maneiras que o mapa de classe N A NA não pode (aparentemente) receber prontamente uma especificação completamente geral e manifestamente natural.$\colon\,$$\,\to\,$

No entanto ...   o comentário de dkuper ( abaixo ) fornece um link para uma palestra de Christos Kapoutsis (LIAFA), intitulada Minicomplexity , que descreve uma estratégia de pesquisa nas linhas indicadas.

Para uma discussão mais aprofundada, um recurso recomendado é a carta perdida de Dick Lipton / Ken Regan Gödel e o ensaio P = NP intitulado Acreditamos muito, mas podemos provar pouco.

A pergunta finalmente feita

A pergunta   Qual característica compartilhada por toda classe de complexidade A ⊂ P, mais rica que NTIME (n ln n), atua para obstruir as provas de A ⊂ NA?

Essa pergunta foi motivada pelos comentários recentes do blog de Scott Aaronson (veja abaixo), e a riqueza teórica da complexidade dessa questão foi posteriormente iluminada pelos comentários / respostas / ensaios de Robin Kathari , Scott Aaronson , Ryan Williams , Dick Lipton e Ken Regan , e perguntas anteriores sobre o TCS StackExchange .

Observações   (1) Para todas as classes de complexidade conhecidas A ⊂ P que são suficientemente grandes para incluir NTIME (n ln n) ⊂ A, o problema A NA está aberto e (2) a razão (s) para esta obstrução teórica da complexidade quase universal não são atualmente bem compreendidos.$\overset{?}{\subset}$

Como muitas pessoas, há muito que apreciei a imensa dificuldade de provar P ⊂ NP, mas não havia apreciado anteriormente que provar A ⊂ NA é um problema aberto para (essencialmente) todas as classes de complexidade computacional.

A pergunta originalmente feita

Em seu blog Shtetl Optimized , Scott Aaronson lançou o seguinte desafio do TCS :

O desafio do Shtetl Optimized TCS    Se você acredita que P vs. NP é indecidível, é necessário responder:

A pergunta Shtetl Optimized TCS    Por que qualquer intuição diz que [ P vs NP é indecidível ] também não diz que as perguntas P versus EXP, NL versus PSPACE, MAEXP versus P / poli, TC0 versus AC0 e NEXP versus ACC são da mesma forma indecidível?

(Caso você não saiba, são cinco pares de classes de complexidade que se provaram diferentes umas das outras, às vezes usando idéias muito sofisticadas.)

Serão aceitas respostas para a seguinte pergunta específica:

Q1 (questão da literatura do TCS)    Alguma classe de complexidade conhecida A e B satisfaz provavelmente A ⊂ B e NA ⊇ B, para NA a extensão natural não determinística de A?

Supondo que a resposta para Q1 seja "sim", é desejável uma explicação de como a prova estrita de inclusão A ⊂ B foi comprovada, enquanto a inclusão estrita (superficialmente semelhante) de P ⊂ NP é difícil de provar.

Como alternativa, se a resposta ao primeiro trimestre for "não", mais uma pergunta é feita:

Q2 ( A questão do TCS otimizado para shtetl estendido ) As inclusões de classe de complexidade da forma geral A and B e NA ⊇ B são prováveis ​​- no ZFC ou em qualquer extensão finita do ZFC - para qualquer classe de complexidade "natural"? (se "sim" construir exemplos; se "não" provar a obstrução).

A satisfação    e os agradecimentos do PostScript são estendidos ao TCS StackExchange por sustentar essa comunidade matemática maravilhosamente inspiradora e útil, e a Scott Aaronson por sustentar seu admirável weblog Shtetl Optimized!

John, enquanto seus amáveis ​​comentários são apreciados, confesso que não entendo como sua pergunta se relaciona com o ponto simples que eu estava fazendo na observação citada. Tudo o que eu estava dizendo era que nós fazer saber várias separações entre classes de complexidade, como P ≠ EXP, MA _EXP ⊄P / poli, NEXP⊄ACC, etc. Então, se você acredita que uma separação particular, como P ≠ NP, é " profundo demais para ser provado ou refutado na teoria dos conjuntos de ZF "(ou seja o que for), parece-me que cabe a você explicar por que você acha que a separação precisa ser independente da ZF, enquanto outras separações acabaram não estar. Para que esse argumento tenha força, não vejo necessidade de as outras separações terem a forma específica que você especificou.

Mas, para responder à sua pergunta de qualquer maneira: bem, o desafio óbvio em responder é encontrar qualquer classe de complexidade A para a qual possamos provar que A está estritamente contido em NA, onde NA é "a extensão não determinística natural de A"! (De fato, como Robin aponta acima, encontrar um A é equivalente a responder à sua pergunta como você a declarou.) E os únicos exemplos desses A que eu consigo pensar são coisas como TIME (f (n)) ( ficou provado na década de 1970 que TIME (f (n)) ≠ NTIME (f (n)) para f (n) ≤n log * n, uma vez que NTIME (f (n)) pode simular um tempo ligeiramente maior que f (n )). (Uma versão anterior desta postagem afirmou que era conhecida por todosf (n). Agradecemos a Ryan Williams pela correção!) Portanto, definir A = TIME (n) e B = NTIME (n) realmente responderia sua pergunta afirmativamente. Um exemplo mais "natural" provavelmente precisará aguardar um avanço na teoria da complexidade.

[Nota de rodapé: Eu gostaria de esclarecer que eu não dar coisas nomes portentosas como "The Shtetl Optimized isto ou aquilo" --- aqueles eram elaborações de sidles!]