Questions tagged [decision-problem]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
144 views

Given the Turing machines M1 and M2, is L (M1) = L (M2)? is decidable?

I thought to reduce from the halting problem to conclude undecidability, yet I don't know how to do it. Perhaps the problem reduces to other decidable problem, and thus it is also decidable?
1
vote
1answer
62 views

show that NP is a subset of decidable languages

More specifically the problem says: "Let us call the set of decidable languages D. Show that NP ⊆ D" My problem is that I always assumed that NP is decidable, but to prove it, I never ...
1
vote
1answer
20 views

Is this “superset existence” problem NP-complete?

The "Superset Existence Problem": Let there be a set $S$, and $x$ subsets of $S$. Does there exist a set of size $y < |S|$, which is a superset of at least $z$ of those subsets? To me, ...
1
vote
1answer
52 views

Understanding P vs NP

I want to make sure my understanding on P vs NP is correct. I know that NP-complete problems cannot be solved in polynomial time, and if P != NP, then all problems in NP cannot be solved in polynomial ...
1
vote
1answer
32 views

Cyclic tour minimizing total weight

I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant. I saw the question below on an old stack exchange question when looking to ...
1
vote
0answers
29 views

Difference longest path problem and underlying decision problem [duplicate]

I am studying the longest path problem with the final objective to show that it is NP-complete. On wikipedia I read that the problem itself is NP-hard but the underlying decision problem is NP-...
0
votes
1answer
56 views

Another version of the 3-coloring decision problem?

Given a graph $G$, is there a 3-coloring with colors $c1$, $c2$ and $c3$ such that at most $k$ nodes are given the color $c1$ and that no two adjacent nodes are given the same color? Is there a ...
1
vote
1answer
33 views

PCP when upper and lower words have different length

The Post correspondence problem (PCP) asks, given two sets of words $a_1,\ldots,a_n$ and $b_1,\ldots,b_m$ over the same alphabet, whether there are indices $i_1,\ldots,i_s \in \{1,\ldots,n\}$ and $j_1,...
0
votes
0answers
19 views

What's the union between a decision problem and its complement

I see the union of problems as something like this: $P=F\cup G$ $P(\omega):$ $\;\;\;\;if\; F(\omega)==True: return \;\; True$ $\;\;\;\;else\;if\; G(\omega)==True: return \;\; True$ $\;\;\;\;else: ...
0
votes
0answers
36 views

Are there any tetrational-time problems?

I know there exists problems decidable in polynomial-time, exponential-time, etc. I couldn't find any tetrational-time problems, however. Are there any and if not, why?
1
vote
1answer
42 views

Is there a #$P$-complete counting problem such that every (valid) instance of its decision version is a Yes-instance?

I want to know whether there is a decision problem, written EasyProblem, satisfying the follow property: For every valid instance $x$, $x$ is a Yes-instance for EasyProblem (if we construct ...
1
vote
1answer
23 views

Different Classes of NP [closed]

I was solving problems related to P and NP where I encountered the following problem: Given a standard definition of NP, if x belongs to L then there exists y such that |y| <= |x|^d and A(x, y) = ...
0
votes
0answers
65 views

3-Sat reduction to facility location problem

I'm learning about NP problems and I this problem which is a bit challenging for me. You are given an undirected, simple graph G = (V,E) and an integer k where nodes represent cities and edges ...
2
votes
0answers
31 views

Proving that DCONN is NL-Complete

I am having trouble with some homework regarding proving that DCONN is NL-Complete. As part of the exercise, the fact that RCH is NL-Complete can be assumed. Problem definitions: RCH: Given a ...
1
vote
2answers
204 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?
0
votes
1answer
42 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 ...
1
vote
1answer
106 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 ...
-1
votes
3answers
188 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 ...
1
vote
1answer
53 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
55 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. ...
1
vote
1answer
51 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, ...
1
vote
1answer
91 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 ...
0
votes
1answer
45 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 ...
-1
votes
2answers
59 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 $\...
0
votes
1answer
58 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 ...
-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
vote
1answer
71 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
64 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
17 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
37 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
22 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. ...
0
votes
1answer
37 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 ...
1
vote
1answer
34 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 ...
3
votes
1answer
294 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 ...
2
votes
1answer
35 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
38 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
80 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
35 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
34 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.
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
134 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$? ...
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
26 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
75 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, ...
0
votes
0answers
42 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
2 3 4 5
9