# Questions tagged [decision-problem]

A question in some formal system with a yes-or-no answer.

519 questions
Filter by
Sorted by
Tagged with
4k views

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

Maybe this is an odd question. It has always bugged me that computability problems are written in all caps, and in such an "awkward" way. SAT, 3-SAT, COLORING, 3-COLORING, PARTITION, CLIQUE, ...
31 views

### If I want to prove that a problem is in NP, can the vertifier use exponential space?

I want to prove that a problem is in NP. I have a witness (of polynomial size), and a verifier that runs in polynomial time. However, this verifier uses exponential space, becuase it has to generate ...
63 views

### Does exist an algorithm that decides whether a program halts or not as its timeout approaches to infinity?

By an algorithm $A(p, t)$ attempting to decide whether the program $p$ halts or not by running the program for $t$ seconds (the timeout) and trying to prove that it doesn't halt at the same time, can ...
35 views

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

Schaefer's dichotomy theorem ensures than when a constraint satisfiability problem satisfies certain conditions, the problem is either in $\mathsf P$ or is $\mathsf{NP}$-hard. Suppose the following ...
101 views

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

A $k$-regular graph is one in which every vertex has degree k. A triangle-free graph is one in which any three vertices do not form a triangle. A dominating set $D$ of a graph $G$ is a set of vertices ...
107 views

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

We proved that, there exist no algorithm so it can tell us if an algorithm halts or not (a.k.a. the halting problem is undecidable). But it surely can handle some of those; can we tell which of those ...
42 views

### Max Unique Clique in $\Sigma^2_p$

I want to prove that the language $\text{Max-Unique-Clique} = \{<G> | \text{The maximal clique of$G$is unique}\}$ is in $\Sigma_2^p$ by using the following $\Sigma_2^p$ machine: The machine ...
282 views

### Constructing equivalent (to a polynomial-time degree) decision problems from function problems

Let's say we're some function problem, $R \subseteq \Sigma^* \times \Sigma^*$, where $\Sigma = \{0, 1\}$ and some oracle $O_R$ that solves $R$. Now, we're given some language, $L \subseteq \Sigma^*$ ...
44 views

### Minimal Hitting Sets Problem

Let $\mathcal{I} = \{I_0, \ldots, I_{m-1}\}$ a collection of subset of some universe $U$. We want to find a partition $P$ of $\mathcal{I}$ of minimal cardinality such that the intersection of each set ...
20 views

### Solving a weighted minimum dominating set problem with its unweighted counterpart?

Question Is it possible to find a solution to the weighted minimum dominating set problem, by solving a (related), unweighted minimum dominating set? Elaboration In essence, can one convert a ...
1 vote
52 views

### Decision version of optimization problems with polynomial-time approximation algorithms

Given an optimization problem $X$, it is easy to construct a decision problem $Y$, such that there is a two-directional polynomial-time reduction between $X$ and $Y$. Therefore, we can define a class ...
59 views

### Why aren't promise problems just decision problems; can't we encode the promised inputs in the alphabet?

I don't really understand why promise problems are classified differently than decision problems. Consider this problem as an example. Given some real number between $0$ and $1$, determine if it ...
105 views

### Ackermann Decision Problem

I have been studying the Ackermann function, specifically the two-argument Ackermann–Péter version. With the Ackermann function, I developed a problem I call the "Ackermann Decision Problem" ...
1 vote
79 views

### Why is 3-co-SAT not in P?

The 3-co-SAT problem consists of deciding whether if a 3CNF formula, has an unsatisfiable assignment of variables, i.e., assignment of variables that evaluates to 0. We know that 3-co-SAT is in coNP, ...
37 views

### Is $\overline{A_{TM}}$ co-NP Hard?

I know that $A_{TM}=\{<M,w>|M~is~a~TM~and~M~accepts~w\}$ is NP-Hard: By showing a polynomial time reduction - $A \le_p A_{TM}$: Let $A \in NP$, then there exists a $NTM$ that decides $A$ in ...
48 views

### Is the set of instances of PCP, which have a solution, semi-decidable?

My idea was that it is because we can construct a TM M' that simulates a TM M that is to find a solution for a PCP instance. M' accepts if M accepts, rejects if M rejects, and doesn't halt if M does ...
39 views

### Integer factorization: Why can't we use the test algorhitm to create an algorhitm to decide the factoring decision problem in polynomial time?

I'm reading Nielsen and Chuang. On page 142 the integer factoring decision problem is introduced: The integer factorization problem can be reduced to a decision problem: Given a composite integer m ...
1 vote
54 views

### The meaning of Tautology and Contradiction in Complexity theory

I recently had this question answered on stack exchange: if X is in NP but Y is not in NP then can X be reduced to Y? The answer proposed a counter example using an element of complexity theory I had ...
63 views

118 views

### Prove minimum vertex bisection problem is reducible from bisection width, thereby proving NP-Completeness

The bisection width problem gives you a yes or a no -> if there exists a bisection of size at most $K$ for $G=V,E$. Minimum Vertex Bisection problem gives you a bisection of the smallest size. ...
544 views