# Questions tagged [decision-problem]

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

547 questions
Filter by
Sorted by
Tagged with
1 vote
46 views

### Non-deterministic TM with an oracle to $R$

Let $R$ be the set of all decidable languages. Consider $P^R$. That is, the set of all languages that can be decided via a polynomial time deterministic TM with an oracle to any language $L\in R$. I'd ...
48 views

### Is the definition of "computational problem" on Wikipedia correct?

In the https://en.wikipedia.org/wiki/Computational_problem, the first line states: "A computational problem is a problem that may be solved by an algorithm." However, I have doubts about the ...
91 views

### Is this "binary submatrix sum equation" problem NP-hard?

There is an unknown matrix $A$ of $R$ rows and $C$ columns. The entry at the $r$-th row, $c$-th column is $A_{rc}$. The matrix is a binary matrix, i.e. each entry is either 0 or 1. Another matrix $B$ ...
• 488
103 views

41 views

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

The membership problem $A_{LBA}$ for a deterministic $LBA$ is decidable because the number of configurations that a $LBA$ can assume is finite. Since this number is also finite for a non-deterministic ...
• 139
1 vote
63 views

### Graph Coloring Decision Problem Reduction to Prove NP-Complete

I am doing research into NP-Complete problems and more specifically started looking into the Graph Coloring Decision Problem or the k-Coloring problem, as described here: Given a graph $G = (V, E)$ ...
• 11
33 views

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

If $G$ is a CFG, is it decidable whether $L(G)=\Sigma^+=\Sigma^*\setminus\{\epsilon\}$? I have no idea which in direction to go. I feel like it is undecidable, but can't seem to find any proof. I ...
1 vote
13 views

### Special case of 2-dim subset sum problem with only 0 and 1s

I am currently researching about a statistical project, where a special computer science problem showed up. I am wondering about the following: Suppose I have many two dimensional vectors all of the ...
30 views

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

A "cosmic kite" of size k consists of a clique of k nodes with a path of k nodes that unfolds from one of the nodes in the clique. Cosmic Kite as decision problem Input: a graph G = (V, E) ...
1 vote
62 views

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

Just curioius, I wanted to know when $S$ ={set of divisors of N} and we're given $N$ a target product. Our goal is to decide if a combination in $S$ has product equal to N. Does the problem remain NP-...
• 321
94 views

### Determining whether two special variants of knapsack have the same optimal value

Given two unbounded knapsack instances, $K_1 = (W_1, weights, values), K_2 = (W_2, weights, values)$, where $W_1 \ne W_2$, what is the complexity of determining $v(K_1) = v(K_2)$ where $v$ returns the ...
1 vote
38 views

### Decidability terms clarification

I just need some clarification regarding the different terms we use in theoretical computer science, especially regarding decidability. Decidable: A language $L$ (a set of strings) is decidable if ...
31 views

• 195
1 vote
31 views

### Complexity class of a problem asking for a chance of receiving an item

I have asked a question on math.SE about if there is a way to do it better than by brute force, but this time I am interested in the complexity of the problem itself. I will repeat the problem, with a ...
• 1,781
34 views

### An Example of the Conjuction of Two NP-Complete Decision Problems Being Polynomial Time Solvable [duplicate]

Firstly, we define A and B as two decision problems with the same set of inputs. Define a new decision problem "A AND B" as follows: The input to "A AND B" is any valid input x for ...
156 views

### Non-deterministic Turing machine that decides the language $L = \{0^{n^2} | n \geq 1\}$

I was trying to figure out how can I construct a non-deterministic Turing machine that decides the language $L = \{0^{n^2} | n \geq 1\}$ I looked at some of the proposed solutions here : Turing ...
• 275
31 views

### How to formulate "The general Sudoku problem is in P" formally and rigorously? How to calculate then the input size?

We consider a partially filled starting grid, where $n^2$ is the side size of the grid, $m$ is the number of non-empty initial squares, $f$ is the function that places randomly initially the integers ...
• 11
30 views

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

$f$ and $g$ being known functions. We suppose that the problem is solvable. To me, for the moment, this question, if a decision problem it is or can be, is more an NP rather than a P problem, because ...
• 11
62 views

### Subset sum reducible to barter economy problem?

I was given the following problem called the barter economy problem: Given a set of $n$ people $\{p_1, \ldots, p_n\}$ and a set of $m$ distinct objects $\{a_1, \ldots, a_m\}$, where each object $a_j$ ...
1 vote
106 views

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

First, can the Navier-Stokes problem be a formal computable one? like a P problem? Then, how to define the corresponding language? Would it only be the set of equations, or something else? Then, could ...
• 11
25 views

I am given a $N$ x $M$ sized grid and $K$ start points $S = (s_1, s_2, .. s_k)$ where each $s_k = (x_k,y_k)$ representing the position on the grid. I am also given a single endpoint $(x_{end}, y_{end})... • 141 2 votes 0 answers 24 views ### Stålmarck's method, can triplets be dropped once they triggered equivalences In Sheeran, Mary, and Gunnar Stålmarck: A tutorial on Stålmarck’s proof procedure for propositional logic there is an example application of the method to... • 98 1 vote 1 answer 65 views ### Do function problems have an interpretation in terms of formal languages? In computational complexity theory, decision problems are typically defined as formal languages, and complexity classes are defined as the sets of the formal languages that can be parsed by machines ... 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 33 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 ... 0 votes 3 answers 118 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 ... • 53 -1 votes 1 answer 49 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,781 2 votes 1 answer 123 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 ... -2 votes 2 answers 122 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 ... • 53 0 votes 1 answer 90 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 ... • 110 2 votes 1 answer 292 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^*$... • 327 0 votes 1 answer 108 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 ... • 173 1 vote 1 answer 85 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 ... • 6,132 0 votes 1 answer 89 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 ... • 243 0 votes 1 answer 142 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 86 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 50 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 ... • 47 1 vote 1 answer 76 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 47 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 63 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 ... 0 votes 1 answer 111 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{...
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. ...