Skip to main content
Share Your Experience: Take the 2024 Developer Survey
26 votes

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 ...
Hendrik Jan's user avatar
  • 30.7k
14 votes

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 ...
Per Alexandersson's user avatar
8 votes

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 ...
mell_o_tron's user avatar
6 votes

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 ...
D.W.'s user avatar
  • 161k
5 votes

Decidability of whether for a given $G$, $L(G)=\Sigma^+$? (or $L(G)=L$ where $L$ is fixed beforehand

It is decidable whether $\epsilon \in L(G)$. Given a context-free grammar $G$, you can construct a new context-free grammar $G'$ such that $L(G')=L(G) \cap \Sigma^+$. If $L(G')=\Sigma^+$ and $\...
D.W.'s user avatar
  • 161k
3 votes

Small doubt concerning cardinality of set of problems and algorithms?

Additionally, I have a bit of trouble understanding the notion of encoding a whole algorithm as a single binary string —is it just an encoding of the finite-tuple-of-finite-sets Turing machine into a ...
Stef's user avatar
  • 530
2 votes

Graph Coloring Decision Problem Reduction to Prove NP-Complete

SAT can be reduced to 3-SAT in a straightforward way (the Tseitin transform), and you seem to be aware that 3-SAT can be reduced to 3-coloring (e.g., https://www.cs.toronto.edu/~lalla/373s16/notes/...
D.W.'s user avatar
  • 161k
2 votes

Decidability terms clarification

Undecidable means "not decidable". They are synonyms. The definition is: we say that $L$ is undecidable if $L$ is not decidable.
D.W.'s user avatar
  • 161k
2 votes
Accepted

Reduce CNF-SAT to decision problem

It is not clear in your solution why treating clauses as groups helps. Note that a satisfying assignment should induce a set of groups and vice versa. Hint: a non direct reduction (but you can start ...
Bader Abu Radi's user avatar
1 vote

Concise definitions for different types of computational problems

A search problem is defined by a verifier $V: \Sigma^* \times \Sigma^* \to \{0,1\}$. Given $x$, the goal is to find $y$ such that $V(x,y)=1$. A counting problem is similar, but given $x$, the goal is ...
D.W.'s user avatar
  • 161k
1 vote

Number of configurations, non-deterministic $LBA$ and $A_{LBA}$

That is correct. A LBA uses bounded space and this can be used to simulate all possible computations (on a fixed input). It is not even necessary to keep track of loops in the simulation, just cutting ...
Hendrik Jan's user avatar
  • 30.7k
1 vote

How do you show that Cosmic Kite Problem is NP complete?

Hint: Reduce from Clique. To every node, connect a path of $k$ vertices.
Pål GD's user avatar
  • 16.5k
1 vote
Accepted

Does the Subset Product Problem remain NP-complete if repetition in S is not allowed?

Let $S = \{s_1,\dots,s_m\}$ (this is a multiset!), without loss of generality not containing any $1$s (if it does, remove them), and let $p_1,\dots,p_m$ be distinct primes which don't divide $N$ or ...
Yuval Filmus's user avatar
1 vote

Transform OTM for Problem π to DTM ∈ DSPACE(n)

It depends on the oracle. If $\pi$ is solved by the OTM using an oracle for a non-computable problem (non-decidable language), then there might not be a DTM that can solve $\pi$ without an oracle. ...
D.W.'s user avatar
  • 161k
1 vote

Is « Does exist at least one function $u$ such that $f(u(0)) \ne g(u(0))$? » an NP problem? or a P problem?

I'm going to assume that $f:A\to B$ and $g:A\to B$ for some (known) sets $A$ and $B$ and that, given a set $C\ni0$ we are to find a function $u:C\to A$ such that $f(u(0))=g(u(0))$. Of course, this is ...
Charles's user avatar
  • 256
1 vote

Subset sum reducible to barter economy problem?

You can reduce from subset-sum as follows: given a set of $n$ positive integers $x_1, \dots, x_n$ and a positive integer target $T$, consider an instance with $2$ people $p_1, p_n$ and $n+1$ objects $...
Steven's user avatar
  • 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 ...
Alex Meiburg's user avatar
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, ...
D.W.'s user avatar
  • 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 ...
Inuyasha Yagami's user avatar
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 ...
Steven's user avatar
  • 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{...
Bader Abu Radi's user avatar

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