0
$\begingroup$

What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat?

Would this result in their being a quasi polynomial-time algorithm for all NP-complete problems?

$\endgroup$
  • 3
    $\begingroup$ What do you think? Have you tried using the definition of NP-completeness? $\endgroup$ – Yuval Filmus Jun 8 at 13:17

Your Answer

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

Browse other questions tagged or ask your own question.