Questions tagged [decision-problem]
A question in some formal system with a yes-or-no answer.
519
questions
19
votes
2
answers
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, ...
- 191
0
votes
1
answer
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 ...
- 13
0
votes
2
answers
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 ...
- 11
-1
votes
1
answer
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 ...
- 1,393
2
votes
1
answer
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 ...
- 25
-2
votes
2
answers
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 ...
- 11
0
votes
1
answer
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 ...
- 100
2
votes
1
answer
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^*$ ...
- 265
0
votes
1
answer
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 ...
- 133
0
votes
0
answers
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 ...
- 123
1
vote
1
answer
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 ...
- 5,790
0
votes
1
answer
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 ...
- 203
0
votes
1
answer
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"
...
- 143
1
vote
1
answer
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, ...
- 23
0
votes
1
answer
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 ...
- 37
0
votes
0
answers
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 ...
0
votes
1
answer
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 ...
- 11
1
vote
1
answer
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 ...
- 29
0
votes
1
answer
63
views
Show that $\text{BOOL-VAL}$ and $\text{DNF-SAT}$ is decidable in linear time
A boolean expression is valid if it is true for every valuation. The problem
$\text{BOOL-VAL}$ asks whether a given boolean expression is valid. As the question suggests I need to show that $\text{...
user153634
0
votes
1
answer
54
views
if X is in NP but Y is not in NP then can X be reduced to Y?
I have been led to believe that the following statement
$X \in NP \land Y \not\in NP \implies X \not\le^m_p Y$
Is True.
But I am having difficult proving it. And I'm not even sure it IS true anymore.
...
- 29
0
votes
2
answers
65
views
Is a language semi-decidable iff it is reducible to ATM?
Thank you. I see how it makes sense going in the opposite direction but i need help proving that this is true.
Below is the definition of ATM.
ATM={<M,w>| a TM, M accepts w}
The question from my ...
- 1
0
votes
0
answers
58
views
Can I find the smallest vertex cover
so this is my question:-
If I manage to find a vertex cover which has ....let's say 100 more vertex than the minimum vertex cover. Can I find the minimum vertex cover in polynomial time from this ...
0
votes
1
answer
67
views
MAX-SAT approximation factor
I am stuck on an exercise that ask the approximation factor of a MAX-SAT approximated algorithm generalized from a MAX-3SAT algorithm
MAX-3SAT:
set every variable with a random value ($0$ or $1$ each ...
- 3
1
vote
1
answer
313
views
NP-Complete Reduction
Prove the following problem is NP-Complete:
The problem gave a directed graph G, and several subsets of vertices of such graph are being specified as T1,T2,....Tn, and the subsects could intersect, ...
- 13
0
votes
0
answers
25
views
Why is the collection of decision problems closed under set operations?
Most of the proofs of such properties that I see involve informally using algorithms or invoking Turing machines as needed. But it's not clear to me how are we using set operations on instances of ...
user153634
-3
votes
1
answer
46
views
Given a list of numbers L and a target k, is there a subset of numbers from L whose product is k?
Is there any dynamic way of solving this problem? I would thank any help, I know the Subset sum Problem, but for solving it dynamically u have to create a matrix but here is not posible as the colums ...
0
votes
0
answers
15
views
Query on kernel existence between related parameters
I am a research scholar working on parameterized complexity. For more information on parameterized complexity please refer to this. I am exploring on the tractability of an NP-complete problem $P$ for ...
- 162
1
vote
1
answer
42
views
Decision tree to check 2 rectangles
Given two disjoint rectangles $(a,b]\times (c,d]$ and $(e,f]\times (g,h]$ in $\mathbb{R}^2$ how can I check with a decision tree of least depth if a given point $(x,y)$ lies within the union of the ...
- 11
0
votes
1
answer
306
views
Does the halting problem belong to NP class of problems?
On the one hand it does not belong to NP problems because it simply is not solvable and is undecidable and on the other hand it is an NP problem because there are claims that it is NP-hard and ...
- 1
2
votes
1
answer
68
views
Is there an algorithm for this decision problem that is better than brute-force?
Apologies for the vague title. This decision problem has applications to graph coloring but I have not found a name for it in the literature.
I am trying to improve my algorithm for a decision problem....
9
votes
2
answers
5k
views
Is SAT an existential question?
Some sources state that an algorithm that solves the SAT problem not only needs to decide whether a given existentially-quantified formula is satisfiable or not, but, additionally, in the case where ...
- 195
1
vote
1
answer
187
views
Graph Isomorphism Problem: decisional vs functional
The Graph Isomorphism Problem is a classic in Computer Science.
In its decision version $(DGI)$, we are given two graphs $G$ and $H$ and we are asked if there exists an isomorphism between the two. In ...
- 133
1
vote
0
answers
52
views
Function problem vs decision problem
I am a mathematician novice with the theory of computer science. During the course I took, we dealt with decisional problems (introducing D, SD, coSD classes language side, and P, NP, coNP, EXP, DP, ...
- 111
0
votes
1
answer
70
views
Are there any formal systems or programming languages in which its only possible to define functions that have inverses?
Consider an algorithm $f(x)$.
Are there formal systems or programming languages that only allow $f(x)$ to be defined if $f^-1(x)$ exists?
- 163
0
votes
1
answer
54
views
Unpacking the notion of "hardest instances" for NP-complete problems
Suppose, for the sake of argument, that it was proved that $P \not= NP$. Then, this would imply that for every $NP$-complete problem, there is a "hardest instance" of the problem that ...
- 271
0
votes
0
answers
56
views
Why don't we consider that NP = co-NP while we can reduce Tautology problem into Satisfiability in polynomail time easily?
Let's determine if an expression is tautological or not and let's try this expression:
((a ⊼ b) ∨ c) ↔ (¬a ∨ ¬b ∨ c).
We can turn this problem into CIRCUIT-SAT decision problem by asking if the ...
- 45
3
votes
1
answer
95
views
Decide whether regular language contains a word $w$ for which $|w| = n^2$
Task:
Input: DFA $M = (Z, Σ, δ, q_S, E)$
$T(M)$ := Language that $M$ accepts.
Question: Does $T(M)$ contain at least one word $w$ such that $|w| = n^2$ with $n \in \mathbb{N}$$ ?$
My attempt:
Since ...
2
votes
1
answer
245
views
Complexity of the (Complete/Assign) 3-SAT problem?
A complete $k$-CNF formula on $n$ variables $(k\le n)$ is a $k$-CNF formula which contains all clauses of width $k$ or lower it implies.
Let us define the (Complete/Assign) 3-SAT problem: Given $F$, a ...
- 511
9
votes
1
answer
2k
views
Why rectangle packing is NP-hard but maybe not in NP?
Recently I studied a MIT open course.
In lecture2, it is stated that Rectangle Packing is NP-hard.
I can understand this because the problem can be reduced to 3-partition problem
But I don't know why ...
- 176
0
votes
1
answer
40
views
Reducing to an NP-complete problem
If $R$ is an arbitrary decision problem that is reducible to $S$, which is an NP-complete problem, what can be said about $R$?
I think we should be able to say that $R$ is in NP since an instance of $...
0
votes
1
answer
56
views
Knapsack with quadratic constraint
Suppose I have a variant of the knapsack problem:
$$\max_{x} \sum_{i=1}^n v_ix_i$$
$$(\sum_{i=1}^n w_ix_i - W)^2 \leq k$$
for $v_i, w_i \in \mathbb{R}$, $x_i \in \{0,1\}$ and $k \in \mathbb{R}, k > ...
- 31
2
votes
1
answer
77
views
NP-completeness of some problems on assigning candidates to departments
Suppose we have $n$ candidates from a candidate pool $\{1,2, .., n\}$ and we have $m$ departments. A candidate can be assigned to at most one department (so not being assigned is possible). Each ...
- 21
-1
votes
1
answer
38
views
What kind of problems in the world can be classified into PSPACE categories?
For instance can we categorize the following problems into NP-Hard ?
Is the Universe finite ?
Is there life after death ?
What came first, the chicken or the egg ?
My question is more around what ...
- 99
1
vote
2
answers
643
views
Prove that a quadratically-constrained linear program (QCLP) is NP-Complete
Show that if we strengthen linear programming by also allowing constraints of the form $$ \sum_{i,j = 1}^n a_{ij} x_i x_j = b,
$$ for integers $b$ and $a_{ij}$, then the problem becomes NP-complete.
...
- 113
0
votes
0
answers
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.
...
- 1
2
votes
3
answers
544
views
Deciding whether an integer polynomial has an integer root
This is a question written by my instructor Z. Loria .
Consider the following problem: Given a polynomial $p(x) = \sum_{i=0}^n a_ix^i$, where $a_i$ are integers, is there a natural number $n \in \...
- 217
1
vote
1
answer
22
views
Condition for detection of collision in an algorithmic problem
While solving This algorithm problem I was unable to come up with condition for the collision to occur ( other than the naive O(n^2) algorithm ) on reading the explanation they say
Let’s deepen the ...
- 219
9
votes
0
answers
196
views
Complexity of frog game on graphs is exponential, or can we do better?
Frog game initializes by placing one frog on every vertex of a simple connected graph $G$ with $n$ vertices. A move consists of moving all $x\gt 0$ frogs from one vertex to another non-empty vertex to ...
- 105
0
votes
0
answers
104
views
Can this kind of NP-Hard problem be approximated?
Consider this kind of optimization problem:
(1) The problem aims to minimize a value. Let n denote this value.
(2) To determine whether n = 0 is a NP-Complete problem.
It is obvious that this kind of ...
- 69
-2
votes
1
answer
41
views
Decision problem
Prove the following theorem
Let A and B be two languages on an alphabet Σ. If A ≤p B and B ∈ P, then A ∈ P.
Could anyone be able to prove it?
- 11