# Tag Info

### Is legislation NP-complete?

It's undecidable because a law book can include arbitrary logic. A silly example censorship law would be "it is illegal to publicize any computer program that does not halt". The reason results for ...
• 12.3k
Accepted

### Why there are no approximation algorithms for SAT and other decision problems?

Approximation algorithms are only for optimization problems, not for decision problems. Why don't we define the approximation ratio to be the fraction of mistakes an algorithm makes, when trying to ...
• 141k
Accepted

### How is the traveling salesman problem verifiable in polynomial time?

NP is the class of problems where you can verify "yes" instances. No guarantee is given that you can verify "no" instances. The class of problems where you can verify "no" instances in polynomial ...
• 80.2k
Accepted

### Is legislation NP-complete?

Laws can include arbitrary language, and arbitrary language is able to express NP-complete logic. So in theory it would be possible to create an NP-complete or even an undecidable law. However, in ...
• 456
Accepted

• 70.9k
Accepted

### The importance of the membership problem

The importance is that any computational problem where the answer is yes or no can be phrased as a membership problem in a language. The language is the set of strings for which the answer is yes.
• 80.2k
Accepted

### Do problems in P have a minimum number of YES and NO instances?

If a problem has only "YES" instances (resp. only "NO" instances), then the associated language, which is our formalization of a "problem" contains every word in $\Sigma^*$ (resp. no words), with \$\...
• 16.2k

### Why there are no approximation algorithms for SAT and other decision problems?

In addition to the existing answers, let me point out that there are situations where it makes sense to have an approximate solution for a decision problem, but it works different than you might think....
• 294