# Questions tagged [decision-problem]

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

64 questions
Filter by
Sorted by
Tagged with
11k views

245 views

### How does one find out whether $N = a^b$ for some $b$?

I was trying to find out how to find whether $N$ is a perfect power or not for some $a$ and $b$ (so the algorithm should discover that its not a perfect power if its not expressable in the form $a^b$)...
2k views

### Is Deciding Decidability Decidable?

I am wondering if deciding the decidability of problem is a decidable problem. I am guessing not, but after initial searches I cannot find any literature on this problem.
6k views

### Do any decision problems exist outside NP and NP-Hard?

This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard. In order to be in NP, problems have to have a ...
3k views

10k views

### All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

My book states this If a decision problem B is in P and A reduces to B, then decision problem A is in P. A decision problem B is NP-complete if B is in NP and for every problem in A in ...
4k views

### Proving that a problem is in NP

I have an assignment in which the problem, $D$, is simple but, once found, easy to check. Is it enough to prove that a solution $x$ can be checked in polynomial time to prove that $D \in NP$? (The ...
1k views

### 3-SAT where variables occur equally many times as a positive literal and as a negative literal

Let $\phi$ be a 3-CNF formula over variables $x_1,x_2,\ldots,x_n$. Every variable $x_i$, $i \in [n]$, occurs equally many times as a positive literal and as a negative literal in $\phi$. Is it NP-...
1k views

### Does every computational problem have a decision version?

Is the following claim correct?: Every computational problem has a decision version of roughly equal computational difficulty. If the above claim is correct, please give a reference for it. (I ...
422 views

### primitive recursive functional equivalence

Given two primitive recursive functions is it decidable whether or not they are the same function? For example lets take sorting algorithms A, and B which are primitive recursive. While there are many ...
3k views

### Optimization problem vs decision problem - reduction

Assume we have an optimization problem with function $f$ to maximize. Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
125 views

### Questions on Graph and Hamiltonian [closed]

From this book and other study in complexity theory, I have seen the following statement: The definition of NP is not symmetric with respect to yes-instances and no-instances. For example, it is ...
624 views

### When is splitting a collection coins two ways NP-complete?

Suppose we have a set $D$ of denominations of coins and a our input is a "tip jar" containing some finite number of these coins (e.g., five nickels, a dime and three quarters). In the first two ...
516 views

### NP-hardness of an optimization problem with real value

I have an optimization problem, whose answer is a real value, not an integer such as vertex cover and set cover. Therefore, the decision version of my problem is given an input and a real value $r$. ...
1k views

### Can the decision version of an optimization problem in NP, be in P?

It is well known that a optimization problem can be turned into a decision problem with an extra parameter: e.g. in TSP we are looking for the lowest cost for a tour, the decision version therefore ...
614 views

### How exactly does a Max 2 Sat reduce to a 3 Sat?

I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after <...
2k views

### Decision version of the traveling salesman problem and NP-hardness

Wikipedia says: The problem has been shown to be NP-hard and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-...
731 views

### Is equivalence of a CFG and an RG undecidable?

I know that the equivalence of two context-free grammars is undecidable, but what about the equivalence of a regular grammar and a context-free grammar?
935 views

### Equivalence of regular grammars

I know that proving context free grammars equivalent is undecidable. I also know that proving if a context free grammar recognizes a regular language is undecidable. Here is my question: is proving ...
2k views

### Decision Problem vs. Optimization Problem [duplicate]

Is the following statement correct? If a decision problem is NP-complete, the corresponding optimization problem can not be solved in polynomial time.
15k views

### Is legislation NP-complete?

I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is ...
2k views

404 views

### Is deciding if there's a solution to a single multivariate quadratic equation NP-hard?

I know that given a system of multivariate quadratic equations (i.e, of the form $x^T Ax+b^T x=c$), deciding if there's a solution is NP-hard. Is deciding if there's a solution to a single ...
2k views

### Reduction: Vertex Cover to Binary Integer Program (Decision Problem)

I am stuck with the following task: Show that the Decision Problem "Vertex Cover" is polynomial-time reducible to the Decision Problem "Binary Integer programming". I have the feeling that there must ...
102 views

### Is there a generic procedure to produce (hard enough) decision problems?

This comment by @DerekElkins suggests a general method of constructing decision problems for problems with bit-strings as output, of which a slightly formalised version is the following: Given a ...
640 views

### Why are decision problems easier than the equivallent optimization problems?

Suppose that we have an optimization problem defined as follows: $OPT$ = Given an input string defining a set of feasible solutions $F$ and an objective function $f$, find $x\in F$ maximizing $f(x)$ ...
717 views

### Do all algorithms aim to solve decision problems?

An algorithm is a “unambiguous specification of how to solve a class of problems... calculation, data processing and automated reasoning tasks” Are the class of problems an algorithm can solve more ...
872 views

### Finding an exactly weighted st-path in a digraph

I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic. The question is: given 2 nodes $v_1$ and $v_2$, is there a ...
39 views

### Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$

$\mathrm{NP}$ has not been separated from constant-depth circuits consisting of solely $\mathrm{Mod}_6$ gates. So, the question is whether current techniques are enough to deduce interestingly ...
271 views

### How does the problem of having a coffee-machine close relate to vertex cover?

Meeting rooms on university campuses may or may not contain coffee machines. We would like to ensure that every meeting room either has a coffee machine or is close enough to a meeting room that ...
4k views

### Examples of undecidable problems whose intersection is decidable

I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the ...
On the wikipedia article about the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A ...