Share Your Experience: Take the 2024 Developer Survey

# Tag Info

### Why are computability problems always written in full caps?

After the Cook-Levin Theorem Richard Karp realized that the complexity of computational problems could be compared. His paper was prepared in a type-writer font, and used underlining and all-caps for ...
• 30.7k

### Why are computability problems always written in full caps?

In the area of discrete mathematics, sets are usually typeset in capital letters. The above problem classes are sets of problems, e.g. SAT is the set of all boolean satisfiability problems. Thus, the ...
• 1,274

### Small doubt concerning cardinality of set of problems and algorithms?

The intuitive reasoning is "there are more problems than algorithms, so it cannot be the case that, for each problem, there exists an algorithm that solves it". More formally, this can be ...
• 287

### Small doubt concerning cardinality of set of problems and algorithms?

Correct. There are only countably many algorithms (only countably many Turing machines). Yes, this proves that there exists at least one decision problem that cannot be decided by any algorithm (in ...
• 161k

• 29.5k
1 vote

### If the Navier-Stokes equations problem is a computable problem, for example a set/language called "L", what are the elements of L?

Languages are a good way of discussing yes or no questions with a finite bit-length input size. There are plenty of alternatives to languages, in complexity theory! They often have some 'moral ...
• 945
1 vote
Accepted

### Schaefer's dichotomy theorem and limits on the formula length

Schaefer's theorem is stated in many places, e.g., on Wikipedia. Can you define a set $S$ of relations so that your problem has the form specified in Schaefer's theorem? No, you cannot. Therefore, ...
• 161k
1 vote
Accepted

### On hardness of finding dominating sets in triangle-free regular graphs

We show that the minimum dominating set (MDS) problem is $\mathsf{NP}$-hard on $3$-regular triangle-free graphs. We show this by a reduction from the bipartite graphs of maximum degree $3$. The MDS ...
• 6,187
1 vote

### Can we tell if we can tell if an algorithm halts or not?

If I understand your question correctly, you are considering an algorithm $A$ that, when run with an input $x$ (which is in turn an algorithm) attempts to predict whether $x$ halts or not. Notice that ...
• 29.5k
1 vote

### Proving that DCONN is NL-Complete

To show that $\text{DCONN}$ is in $\text{NL}$: you can use the fact that $RCH\in \text{NL}$ and the fact that $\text{NL} = \text{coNL}$. So we have a nondeterministic TM $T$ that decides \$\overline{...
• 2,931

Only top scored, non community-wiki answers of a minimum length are eligible