# Questions tagged [decision-problem]

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

414 questions
Filter by
Sorted by
Tagged with
10 views

### Let $L \in \mathrm{\mathbf{NP}}$, is there a polynomial-time oracle Turing machine $B$ that $B^{L}$ on input $x \in L$ outputs a certificate for $x$?

Let $L \in \mathrm{\mathbf{NP}}$ and a verifier Turing machine $M$ for $L$. Is there a polynomial-time oracle Turing machine $B$ that $B^{L}$ on input $x \in L$ outputs a certificate for $x$ (with ...
190 views

### NP-completeness of testing whether a SAT formula does not contain any redundant clause

This paper explains that testing the irredundancy of a SAT instance is NP-complete. But I don't understand the theorem/reduction. How would one reduce 3SAT or k-SAT to this problem, for example?
33 views

### If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?

This question boils down to: If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor? Let's take the Traveling ...
78 views

### How to convert a decision tree to an automaton?

From what I know, a problem can be transformed to a yes/no answer, which can be described by a decision tree. Solution to a problem also can be represented by a set of strings (a language), which ...
15 views

### What does a kernel of size n,n^2 ,… mean?

So according to Wikipedia, In the Notation of [Flum and Grohe (2006)], a ''parameterized problem'' consists of a decision problem $L\subseteq\Sigma^*$ and a function $\kappa:\Sigma^*\to N$, the ...
164 views

### Why don't passwords prove P != NP?

Pardon my ignorance on the matter but, Verifying passwords = Polynomial (linear) Guessing passwords = Exponential Since each guess has nothing to do with one another, exponential time is best possible ...
52 views

### Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable?

I want to ask if $\{w|\forall x\in T(M_v):|w|>|x|\}$ is decidable if v is a Index of a random but fixed Turing Machine with $|T(M_v)|<\infty$. My idea: It is co-semi-decidable since as soon as i ...
53 views

### Is the problem that determines whenever the word member $\in$ L(M) decidable or not?

Given a Turing machine M on alphabet {m,e,b,r} we're asked to determine if member $\in$ L(M). You must realize that M is not one specific machine and can be any turing Machine with the same alphabet. ...
43 views

### Rice's Theorem for Turing machine with fixed output

So I was supposed to prove with the help of Rice's Theorem whether the language: $L_{5} = \{w \in \{0,1\}^{*}|\forall x \in \{0,1\}^{*}, M_{w}(w) =x\}$ is decidable. First of all: I don't understand, ...
78 views

### Enumerator for Word and Halting Problem

in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I ...
42 views

### Why is the Halting problem decidable for Goto languages limited on the highest value of constants and variables?

This is taken from an old exam of my university that I am using to prepare myself for the coming exam: Given is a language $\text{Goto}_{17}^c \subseteq \text{Goto}$. This language contains exactly ...
51 views

21 views

### Pick elements that don't exhaust any set

The following is an NP-Complete problem: Suppose you have a collection $\mathcal{C}$ of sets, so that $A_i\in \mathcal{C}$ and $A_i$ is some set--we can suppose the elements of $A_i$ are integers. ...
36 views

### Is $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} (un-)decidable?

I have to prove that the language $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} is (un-)decidable. In a previous assignment we proved that $L_1:=${$<M>$|$L(M)=A_TM$} is undecidable. I would say ...
31 views

### why is $\Pi_2$ smaller than $NP\cap coNP$

Consider the language $A=\{(\phi_1, \phi_2) | \phi_1 \in SAT, \phi_2\in \overline{SAT} \}$. What is the smallest class that $A$ is known to belong to? Apparently, the answer is $\Pi_2$, although I ...
267 views

### A variation of the halting problem

Given an infinite set $S \subseteq \mathbb{N}$, define the language: $L_S = \{ \langle M \rangle : M$ is a deterministic TM that does not halt on $\epsilon$, or, $T_M \in S\}$ where $T_M$ is the ...
25 views

### Why minimum vertex cover problem is in NP

I am referring to the definition of the minimum vertex cover problem from the book Approximation Algorithms by Vijay V. Vazirani (page 23): Is the size of the minimum vertex cover in $G$ at most $k$? ...
37 views

### checking whether turing machine passes at least k>2 states before accepting a word

$L=\{\langle M,k\rangle \mid\exists w\in L(M) \text{ such that$M$passes at least$k>2$distinct states before accepting$w$}\}$ I try to think of reduction to prove that this language is ...
54 views

### Variant of Subset-sum has an $O(1)$ algorithm if $Goldbach$ is true

Given $S$ of positive integers $>$ $1$ is there some combination with even $SUM$ > $2$ that is NOT the sum of two primes? $SUM$ = 10 $S$ = $[4,6]$ $No$, Sum of Two Primes $5 + 5 = 10$. ...
71 views

### Complexity of Integer Factorization

In Quantum Information and Quantum Computation by Nielsen and Chuang, they define the complexity class NP as follows (page 142): A language $L$ is in NP if there is a turing machine $M$ with the ...
47 views

### An optimization version of 2QBF: is it $\mathsf{NP}^{\mathsf{NP}}$-hard?

I am studying the computational complexity of the following decision problem related to 2QBF: Input: a 3-CNF formula $\varphi$ over $X \cup Y$, where $X$, $Y$ are disjoint sets of propositional ...
32 views

### Why Right-Division of regular language with RE\E language is regualr?

I think I can't understand the meaning of language being decidable. The next case makes no sense to me: Considering I have language L1 which is regular, and language L2 which is in RE\R (in ...
33 views

### Is necessarily the following language not decideable

For A,B that are not decidable, does AB U BA not necessarily decidable? I think that the answer is NO. Not necessarily. I thought about the following example, but it does not refute exactly: If we ...
19 views

### What decision problems are their that are outside of elementary but still decidable

What decision problems are their that are outside of ELEMENTARY but still decidable? I'm curious about problems that are still solveable, but take a very long time to do so.