0
$\begingroup$

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 ?

$\endgroup$
  • 2
    $\begingroup$ I don't know what "Does indirect diagonalization a relativized proof?" means. (Also, "relativization" isn't something you solve a problem with.) Finally, it's not clear what you mean by "indirect diagonalization", or what is DTISP or SC or A, or what it means for a class to be "big". I suggest editing the question to state what you are trying to say more carefully and precisely. $\endgroup$ – D.W. Aug 28 '18 at 21:46
  • $\begingroup$ thanks. My main question is can with R.kanon , Fortnow ,... technique that shows lower bounds for SAT seperate P and NP? $\endgroup$ – Mohsen Ghorbani Aug 29 '18 at 5:22
  • $\begingroup$ cstheory.stackexchange.com/questions/6575/… $\endgroup$ – Mohsen Ghorbani Sep 2 '18 at 9:03
1
$\begingroup$

Buss and Williams codified the technique in their paper Limits on alternation-trading proofs for time-space lower bounds, and showed that the best bound that it can give is that SAT cannot be solved in time $n^{2\cos(\pi/7)}$ and space $n^{o(1)}$. This bound had been achieved earlier by Williams in his paper Alternation-Trading Proofs, Linear Programming, and Lower Bounds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.