new | show | ask | jobs Github

caughtinthought 8 hours ago

3SAT can't be solved in sub-exponential time

Fwiw never thought it was a well-named conjecture

▲

pcstl 8 hours ago | parent [-]

*Can be solved

This proves that EXP != NP

▲

jibalt 5 hours ago | parent | next [-]

This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.

Note https://news.ycombinator.com/item?id=50253213 which explains it better.

▲

caughtinthought 8 hours ago | parent | prev [-]

I'm stating the conjecture as requested

▲

pcstl 7 hours ago | parent [-]

I think you misunderstood, I believe they were requesting a layperson-friendly explanation of the conjecture and not a statement of it.

	▲	jibalt 5 hours ago \| parent \| next [-]
		How is "This proves that EXP != NP", which is false, a layperson-friendly explanation of the actual proof that 3SAT is sub-exponential? Note https://news.ycombinator.com/item?id=50253213
	▲	moishe_syzslak 7 hours ago \| parent \| prev \| next [-]
		Whenever someone asks for an ELI5, there's always got to be somebody who further confuses the issue.
	▲	caughtinthought 7 hours ago \| parent \| prev [-]
		Which is a separate issue than the one you commented originally