I think the intuition is to disprove this by counter example, but what are 2 specific well known problems I can use as counter example?

  • $\begingroup$ Can you please list as least one problem that you do know? $\endgroup$ – John L. Apr 18 at 12:22
  • $\begingroup$ I think I can use 1 SAT vs 3 SAT, 1 SAT can reduce to 3 SAT by setting all clauses to contain only x and not x, but 3 SAT can't reduce to 1 SAT. $\endgroup$ – ChaiTea Apr 23 at 2:37

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.