Subset Sum & Tautology

 

Subset Sum

We can say that subset sum is in NP:

·         Given a subset of numbers from S, we can check that they add up to k

However, there is no known algorithm to solve subset sum in polynomial time. We simply do not know if it is in P.

Perhaps more interestingly: the above verification process relies on the existence of a subset which adds up to k. This means that it can only work with yes instances of the problem. There is no known equivalent procedure to check no instances of the problem. We simply do not know if subset sum is in Co-NP either!

The subset sum problem is in NP because we can verify a "yes" instance (i.e. a subset that adds up to the target value) in polynomial time by checking the sum of the subset. However, it is not known whether the problem can be solved in polynomial time, so it is not known whether it is in P. Additionally, as you mentioned, there is no known equivalent procedure to verify "no" instances of the problem, so it is not known whether the subset sum problem is in co-NP. This means that the subset sum problem is an example of a problem that is in NP but not known to be in P or co-NP.

Tautology

In logic and mathematics, a tautology is a formula that is always true, regardless of the values of its variables. For example, the formula "A or not A" is a tautology, because it is true no matter what value A takes. In computer science, the problem of determining whether a Boolean expression in disjunctive normal form (DNF) is a tautology is known as the tautology problem.

The tautology problem involves evaluating a given Boolean expression for all possible combinations of inputs and determining whether the expression always evaluates to true. For example, given the Boolean expression (A ∨ ¬A) ∧ (B ∨ ¬B), we can evaluate the expression for all possible combinations of A and B and check whether it is always true. In this case, the expression is a tautology, because it is true for all combinations of A and B.

The tautology problem is an example of a decision problem, because it involves determining whether a given instance has a certain property (being a tautology) or not. It is potentially easier to determine that a "no" instance of the tautology problem is indeed a "no" instance, because this can be done by simply checking all possible combinations of inputs and seeing if the expression ever evaluates to false. On the other hand, determining that a "yes" instance is indeed a "yes" instance may require evaluating the expression for all possible combinations of inputs, which could be more computationally expensive.

Similarly, we can say that tautology is in Co-NP:

·         Given a suitable truth assignment for the variables in the formula, we can check that it evaluates to false.

However, there is no known algorithm to solve tautology in polynomial time. We simply do not know if it is in P.

Again: the above verification process relies on the existence of a truth assignment which evaluates to false. This means that it can only work with no instances of the problem. There is no known equivalent procedure to check yes instances of the problem. We do not know if tautology is in NP!

It is worth noting that, while we do not know if tautology is in NP, we do know that it is in the larger class of problems known as PSPACE (polynomial space). This means that it can be solved using a polynomial amount of memory, even if it may require an exponential amount of time to solve.

Food for thought...

This problem (like many in compsci) is related to Tautology.

Given any Boolean circuit C, is there a circuit with equivalent output using k gates or less.

Is it in P?

Is it in NP?

Is it in Co-NP?

You probably used to solve (very) small instances of this as an undergraduate, using Karnaugh Maps - but think very carefully about the general case.  

This problem is related to tautology in that it involves determining whether a given Boolean circuit has a certain property (using k gates or fewer). However, it is a different problem, and its complexity class is not necessarily the same as tautology.

It is not clear whether this problem is in P, as it is not known whether there exists an algorithm that can solve it in polynomial time. Similarly, it is not known whether this problem is in NP, as it is not known whether there exists a witness that can be used to verify a "yes" instance of the problem in polynomial time. It is also not known whether this problem is in co-NP, as it is not known whether there exists a witness that can be used to verify a "no" instance of the problem in polynomial time.