1
$\begingroup$

I'm currently following a course and we have to prove that a restricted version of the 3-SAT decision problem where each literal appears at most once is solveable in polynomial time.

I think such a problem is always satisfiable since we can just assign any sub-expression the needed truth value without it interfering with the rest of the expression. My reasoning is that if we have any literal $p$ we can freely assign any truth value without interfering at all with any other part of the expression since $p$ is guarantied to not occur in any other part of the expression.

I don't think that is what my professor meant so I am wondering whether my reasoning is correct or what I am doing wrong.

$\endgroup$
0

0