Questions tagged [decision-problem]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
21 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 ...
1
vote
2answers
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?
3
votes
1answer
150 views

Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable

Consider the following problem: given a lambda calculus term $t$ and free variable $v$ determine whether $\phi(t,v)$, where $\phi(t,v) := \exists t'. t' \equiv t \land v \notin FV(t')$. This problem ...
2
votes
1answer
68 views

How To Show That B is Semi-Decidable Given A

I am preparing for my Computational Theory final and ran into this exact problem : B={ x | there exists a prefix of x that is in A}. Show that B is semi-decidable. In other words, you need to ...
0
votes
1answer
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 ...
3
votes
3answers
2k views

Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

I am studying "An Introduction to the Theory of Computation" by Sipser -- there is a problem *3.17 (p.161) which I can not solve. Any hints (not answers) from which side to attack it? Let $B=\{M_1,...
8
votes
2answers
2k views

Decidability of halting problem for DPDAs with $\epsilon$-transitions?

For LBAs it's rather easy to prove the decidability of the halting problem, as there can only be a finite number of different configurations when using limited space. But what about PDAs with $\...
1
vote
1answer
82 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 ...
0
votes
1answer
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 ...
21
votes
4answers
1k views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
0
votes
1answer
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 ...
1
vote
1answer
222 views

Solve Max 3 color problem using 3 color decision problem

I've been stumped on this question for a while and can't find a solution. How can I find the max 3 colorability of a graph(optimization problem) with 3 colorability (decision problem) without brute ...
0
votes
1answer
43 views

Turing-completeness of Goto language with limited constants

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} \subseteq \text{Goto}$. This language includes exactly ...
-1
votes
3answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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. ...
3
votes
1answer
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 ...
1
vote
1answer
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, ...
0
votes
1answer
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 ...
-3
votes
1answer
95 views

I have a decision problem with $2^n$ bit sized certificates, how would I verify my decision problem efficiently if it is in $NP$?

Decision Problem: Is $2^k$ + $M$ a prime? The inputs for both $K$ and $M$ are integers only. The solution is the sum of $2^k$+$M$. (Use AKS to decide prime) The powers of 2 have approximately $2^n$ ...
-1
votes
2answers
52 views

Proof: is the language $L_1=\{\langle M\rangle\mid\emptyset \subseteq L(M)\}$ (un)-decidable?

I want to show that $L_1 = \{\langle M\rangle \mid \emptyset \subseteq L(M)\}$ is decidable/undecidable - without rice theorem (just for the case that I can apply it). Every language contain the $\...
1
vote
1answer
46 views

Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP

In this paper (https://arxiv.org/pdf/1706.06708.pdf) the authors prove that optimally solving the $n\times n\times n$ Rubik's Cube is an NP-complete problem. In the process, they must show that the ...
0
votes
1answer
39 views

Every decidable language $L$ has an infinite decidable subset $S \subset L$ such that $L \setminus S$ is infinite

Given an infinite decidable language $L$, then if $S \subset L$ such that $L \setminus S$ is finite, then $S$ must be decidable. This is true since given a decider of $L$ we contruct a decider for $S$:...
0
votes
2answers
16 views

Proof of Co-Problem being in NP if Problem is in NP using negated output

Given any problem $P$ that we know of being in $NP-\text{complete}$, where is the flaw in the following proof? Given a problem $Co-P$ which is the co-problem of $P \in NP-\text{complete}$, $Co-P$ is ...
1
vote
2answers
32 views

Computing automaton for $L(A) / L(B)$ gives ones for $A,B$

I'm trying to figure out whether infinite language change the answer. Show that the following language is decidable: $$L=\{\langle A,B \rangle : \text{$A,B$ are DFAs, $L(B)$ is finite, and $L(A)/ L(B)...
0
votes
1answer
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 ...
0
votes
1answer
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. ...
1
vote
1answer
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 ...
2
votes
1answer
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$? ...
0
votes
1answer
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 ...
0
votes
1answer
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$. ...
2
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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.
1
vote
1answer
884 views

Decidability of determining whether a context-free grammar generates all strings in 1*

How could I prove that the following language is decidable? $\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$ P.S. It's the problem 4.15 of the third ...
0
votes
0answers
49 views

Would this algorithm fail to count solutions $>$ $1$ for Exact-3-cover?

Decision Problem: Given a set $S$, is there at least a given $N$ $>$ $1$ amount of solutions, for an $Exact~Cover~by~3-sets$ for $C%$? $s$ = $1,2,3,4,5,6$ $c$ = $[[1,2,3],[4,3,2],[4,5,6],[5,1,6],[...
2
votes
1answer
130 views

Combining 2 problems in NP into one

Say I have a deterministic turing machine which solves decision problem S with oracle access to both problems B, C that are in $NP$. Can S be solved with oracle access to only one problem in $NP$? ...
1
vote
3answers
129 views

What does “Every CFL is decidable” exactly mean?

I am trying to prove the fact that every CFL is decidable, however I can't come to terms with what the statement exactly means. I know that generation of a particular string by a given CFG is a ...
0
votes
1answer
26 views

Is there a polynomial time algorithm for this decision problem?

Is there a factor in $M$ that is $>$ $1$, but $<$ $M$ that is NOT a factor of $N$? False Result Example $N$ = 8 $M$ = 16 1, 2, 4, 8, 16 There is no integer that is NOT a factor of $N$ that ...
0
votes
1answer
30 views

If a decision problem is in $P$, must finding the solution be possible in polynomial-time?

Function Problem that finds the solution Given integer for $N$. Find $2$ integers distinct from $N$. (But, less than $N$) That have a product equal to $N$. This means we must exclude integers $1$ ...
0
votes
1answer
24 views

Longest palindrome substring in logarithmic runtime complexity

In a palindrome of size N, the amount of candidates for the longest palindrome is N^2. Therefore, the information theoretic lower bound (IBT) should be lg(N^2), which is equivalent to a runtime ...
1
vote
2answers
69 views

Are NP proofs limited to polynomial length?

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, ...
1
vote
0answers
72 views

Prove that a 3D packing problem is NP-complete

How can I prove that the following problem is NP-complete? I have a spherical container in which I have to introduce $n$ identical spheres. All of the little spheres have to be inside the container ...
0
votes
0answers
40 views

Given a CFG and one of its nonterminals $v$ determine if there exists a sentential form beginning with $v$?

I am supposed to find an algorithm solving the following problem: Given a CFG $\;G=(V_N, V_T, R, S)$ and a nonterminal $v \in V_N$ determine if there exists a sentential form which begins with $v$. ...
1
vote
1answer
44 views

Karp reduction from optimization problems to decision problems

When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other. Focusing on Cook reductions, there exists a natural Karp ...
0
votes
0answers
14 views

Search reduction to decision

I'm a little stumped on this question (and I don't know the name of it, which is why I've excluded it from the title). I need to describe an algorithm that finds a solution to an NP-Hard problem given ...
1
vote
1answer
58 views

Can all types of computational problems be modeled as decision problems?

Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision ...
1
vote
1answer
44 views

How does the length of the output of a problem inform its complexity?

Consider the decision problem: Subset sum. For an input set of integers, it asks for a Yes/No answer to the question of whether or not we can find a subset of elements of this input that add up to 0. ...

1
2 3 4 5
9