New answers tagged reductions
3
No. The gamer will basically have to work out the SAT problem in their head.
Think of any video game puzzle you've solved that wasn't easy. You probably solved it by working out a simpler version of the problem and then solving that. If you "complexify" SAT into a video game level, the best way to solve the video game level will be to simplify it ...
1
Given a SAT instance A, another SAT instance B can be constructed such that if it is found satisfiable the satisfying assignment proves the unsatisfiability of A. But the proof is one-sided; if B is found to be unsatisfiable that in itself does not prove that A is satisfiable.
This is accomplished by crafting B's clauses such that its variable assignments ...
1
There is a reduction proof here, with a lot of context:
https://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/22/Small22.pdf
In short, the reduction is:
Let the machine $M'$ be defined as follows:
$M'$ = On input $⟨N, z⟩$:
Run $N$ on $z$.
If $N$ halts on $z$, accept
We run on $⟨M', ⟨M, w⟩⟩$, and get that $⟨M, w⟩ \in HALT_{TM} \iff ⟨M', ⟨M, w⟩⟩...
Top 50 recent answers are included
