Pergunta

My main question is can with R.kanon , Fortnow ,... technique that shows lower bounds for SAT seperate P and NP ?

Baker-Gill-Solovay showed that $P?=NP$ could not be solved with relativization. Does indirect diagonalization a relativized proof?

Suppose with indirect diagonalization we show that $NP\not\subset A$ (A is an arbitrary class). how $A‌$ class can be big with indirect diagonalization technique?(I know it is possible that $TISP(n^{1.8},polylog n)=P$ and the bigger class for me is P or $TISP(n^{O(1)},polylog n)=P$ ). we know that $A$ is at least $TISP(n^{1.8},polylog(n))$(class of languages decides with $O(n^{1.8})$ time and $O(polylog(n))$ space simultaneous).

According to Baker-Gill-Solovay proof I think this approach can not seperate P and NP with indirect diagonalization according this pdf. that mentioned "we will show that such techniques alone cannot prove NP=P"

In special case I want to know that if someone shows $NP\not \subset TISP(n^{O(1)},poly(\log(n)))$ with indirect diagonalization ?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top