Por que não usamos classes maiores para estudar determinismo versus não determinismo?

Em uma pergunta anterior sobre hierarquia de tempo, aprendi que as igualidades entre duas classes podem ser propagadas para classes mais complexas e as desigualdades podem ser propagadas para classes menos complexas, com argumentos usando preenchimento.

Portanto, uma pergunta vem à mente. Por que estudamos uma pergunta sobre diferentes tipos de computação (ou recursos) na menor classe (fechada) possível?

A maioria dos pesquisadores acredita que . Essa distinção de classes não seria entre classes que usam o mesmo tipo de recurso. Portanto, pode-se pensar nessa desigualdade como uma regra universal: o não determinismo é um recurso mais poderoso. Portanto, embora seja uma desigualdade, ele pode ser propagado para cima através da exploração da natureza diferente dos dois recursos. Portanto, pode-se esperar que também. Se alguém provasse essa relação ou qualquer outra desigualdade semelhante, isso se traduziria em . $P \neq NP$ $EXP \neq NEXP$ $P \neq NP$

Meu argumento talvez se torne claro em termos de física. Newton teria dificuldade em entender a gravidade universal examinando rochas (maçãs?) Em vez de corpos celestes. O objeto maior oferece mais detalhes em seu estudo, fornecendo um modelo mais preciso de seu comportamento e permitindo ignorar fenômenos de pequena escala que podem ser irrelevantes.

Certamente, existe o risco de que em objetos maiores haja um comportamento diferente; no nosso caso, o poder extra do não-determinismo não seria suficiente em classes maiores. E se, afinal, o estiver comprovado? Devemos começar a trabalhar no no dia seguinte? $P \neq NP$ $EXP \neq NEXP$

Você considera esta abordagem problemática? Você conhece pesquisas que usam classes maiores que o polinômio para distinguir os dois tipos de computação?

cc.complexity-theory big-picture chazisop
fonte

Penso que as mesmas barreiras que dificultam a prova de P! = NP também dificultam a separação de EXP e NEXP. Por exemplo, acredito que exista um resultado de não relativização para EXP e NEXP. Tenho certeza de que as pessoas consideraram questões de separação em relação a classes de complexidade maior, mas eu imagino que isso não tenha levado a mais progressos do que tentar separar as menores.

Philip White

Acabei de reler seus últimos parágrafos; Eu posso ter interpretado mal sua pergunta. Você está perguntando: "por que não podemos separar P! = NP examinando conjecturas relacionadas como EXP! = NEXP?" ou você está perguntando: "por que P? = NP foi escolhido em vez de uma pergunta diferente para explorar as diferenças entre determinismo e não determinismo?" Suponho que você saiba que P = NP -> EXPTIME = NEXPTIME. A resposta para a segunda pergunta, eu acho, está relacionada ao fato de que P é viável, enquanto EXPTIME não é. Além disso, o NP é relevante para a criptografia. Eu acho que P? = NP parece mais "relevante".

Philip White

A segunda pergunta é minha pergunta principal. No entanto, a primeira pergunta também está relacionada: podemos separar o não-determinismo do determinismo de uma vez por todas ou estamos fadados a tentar resolver infinitas questões P! = NP, sempre com classes maiores? Também estou argumentando que, embora P e NP são relevantes para os nossos problemas "humanos", classes talvez maiores que são inviáveis são necessários para entender o poder do não-determinismo

chazisop

Respostas:

O problema pode ser um pouco mais limpo com e . A maneira mais fácil de pensar sobre essas classes é que elas são iguais a e mas restritas a idiomas unários . Ou seja, todas as entradas têm o formato . $E=Dtime(2^{O(n)})$ $NE=Ntime(2^{O(n)})$ $P$ $NP$ $1^k$

Ou seja, a linguagem está em , se e apenas se o idioma é em (identificação de cordas com números utilizando a representação binária), e de modo semelhante é isomorfa a unária . $L$ $E$ $U_L = \{ 1^x : x\in L \}$ $P$ $NE$ $NP$

Portanto, tentar separar de é como tentar não apenas separar de , mas fazê-lo usando uma linguagem unária. Não há razão para facilitar sua vida conceitualmente. $NE$ $E$ $P$ $NP$

Boaz Barak
fonte

Isso parece esclarecer a situação. Então, pode-se dizer que

implica que não há algoritmo geral que permita uma simulação polinomial de um NTM por um DTM, enquanto declarações semelhantes para classes maiores implicam a mesma declaração, mas para linguagens mais específicas?

P \neq N P

$P \neq NP$

chazisop

Sim, de fato ele faz (para as famílias mais restrito de línguas)

Boaz Barak

Por que escolhemos nos preocupar com vs. ? Na verdade, o não determinismo como objeto de estudo é apenas uma preocupação secundária. Nós realmente se preocupam com por causa dos milhares de importantes problemas que são -completo. Estes são os problemas que queremos (e na vida real precisamos ) resolver. Preocupamo-nos se esses problemas podem ser resolvidos com eficiência, e é o nosso modelo teórico para computação eficiente. Daí que são conduzidos para a questão de vs. . $P$ $NP$ $NP$ $NP$ $P$ $P$ $NP$

Kristoffer Arnsfelt Hansen
fonte

Note-se que não são conhecidos separações para algumas classes de complexidade sem limites, por exemplo, , e também igualdades como e $decidable \neq computability \ enumerable$ $NPSpace = PSpace$ $primitive \ recursive = nondeterministic \ primitive \ recursive$ . (É instrutivo pensar por que o preenchimento trivial usá-los não é útil para a resolução de P vs NP.) Devemos ter mais cuidado sobre o que queremos dizer com uma pergunta como vs e vs . Se vs é uma versão acolchoada (por exemplo, vs e vs ), a resposta de Boaz também se aplica a ela. $P$ $NP$ $EXP$ $NEXP$ $P$ $NP$ $EXP$ $NEXP$ $E$ $NE$

A evidência para é muito mais fraca que e tem consequências menos dramáticas, e há pessoas que acham plausível, então a situação é mais complicada e temos uma intuição muito mais fraca sobre a resposta esperada. Uma igualdade não ajudará na prática e não é conhecido por ter um efeito no caso realmente interessante que é vs , e uma desigualdade é formal e conceitualmente tão difícil quanto uma desigualdade entre $EXP \neq NEXP$ $P \neq NP$ $EXP = NEXP$ $P$ $NP$ vs . $P$ $NP$

Kaveh
fonte

implica

, então não entendo sua afirmação de que a evidência para

é muito mais fraca. Observe que

implica que

que é um resultado muito surpreendente.

E X P \neq N E X P

$EXP \ne NEXP$

P \neq N P

$P \ne NP$

E X P \neq N E X P

$EXP \ne NEXP$

E X P = N E X P

$EXP = NEXP$

N E X P = c o - N E X P

$NEXP = co-NEXP$

Mohammad Al-Turkistany

@turkistany: Obrigado pelo comentário (embora eu não ache um bom motivo para votar). I pensado que era clara,

implica

mas não vice-versa, por conseguinte, uma evidência para

não parece ser uma evidência para

. De qualquer forma,

seria muito menos surpreendente do que

E X P \neq N E X P

$EXP \neq NEXP$

P \neq N P

$P \neq NP$

P \neq N P

$P \neq NP$

E X P \neq N E X P

$EXP \neq NEXP$

E X P = N E X P

$EXP=NEXP$

P = N P

$P=NP$ você não concorda?

Kaveh

@ Kaveh, deixe-me discordar. Acho

um resultado muito surpreendente, porque implica

como afirmei acima.

E X P = N E X P

$EXP = NEXP$

N E X P = c o - N E X P

$NEXP =co-NEXP$

Mohammad Al-Turkistany

@turkistany: Está claro para mim que

seria muito mais surpreendente do que

, mas com certeza, você pode discordar disso. :)

P = N P

$P = NP$

E X P = N E X P

$EXP=NEXP$

Kaveh

Como você define recursiva primitiva não determinística?

slimton