Questions tagged [decision-problem]
A question in some formal system with a yes-or-no answer.
538
questions
0
votes
1
answer
265
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 ...
- 109
0
votes
1
answer
61
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$.
...
- 57
2
votes
1
answer
257
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 ...
- 123
2
votes
0
answers
64
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 ...
- 95
1
vote
1
answer
127
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 ...
- 109
0
votes
1
answer
35
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 ...
- 109
0
votes
0
answers
51
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],[...
- 57
2
votes
1
answer
306
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$?
...
- 51
0
votes
1
answer
56
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 ...
- 57
0
votes
1
answer
38
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$ ...
- 57
0
votes
1
answer
46
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 ...
- 3
0
votes
2
answers
184
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, ...
- 401
0
votes
0
answers
50
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
1
vote
1
answer
311
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 ...
- 121
1
vote
0
answers
164
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 ...
- 11
2
votes
3
answers
5k
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 ...
1
vote
1
answer
72
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. ...
- 296
7
votes
1
answer
1k
views
Algorithms that run in polynomial time if P=NP
On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking ...
- 289
1
vote
0
answers
25
views
Is there a recursive problem encoding the Turing completeness of a model of computation?
Suppose we have a model of computation $C$ we want to show to be Turing complete. The usual strategy would be to emulate within $C$ any model of computation we already know to be Turing complete (e.g. ...
- 111
1
vote
1
answer
249
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 ...
- 345
1
vote
0
answers
149
views
Decision Making using Multiple Variables
What should I learn if I want to make a decision based on multiple variables? Followings are the example of a problem.
I have a farm. My variables are weather, humidity of air, humidity of soil, size ...
- 111
0
votes
1
answer
740
views
Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC
i don't understand the following:
If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting ...
- 73
0
votes
0
answers
106
views
What is the strongest arithmetic theory decidable by a DFA, DPDA or PDA?
It is known that WS1S can be decided by a DFA. Is this the strongest arithmetic theory decidable by a DFA? What happens when the automata class is extended to include DPDAs or PDAs?
- 123
1
vote
2
answers
567
views
A special case of subset sum
I came across the following problem in my complexity-theory course:
Given a set of numbers $A := \{a_1, \dots, a_n\} \subset_{\mathrm{finite}} \mathbb{N}$ and a number $b$ also in $\mathbb{N}$ such ...
- 13
0
votes
1
answer
151
views
NP-completeness for integer linear program
This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come ...
user106782
2
votes
2
answers
607
views
How to prove LastToken problem is NP-complete
Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding ...
- 361
0
votes
0
answers
64
views
Restriction: polynomial time decision of instance is why needed to "decision Problem"?
I am reading book "combinatorial optimization 3rd edition(Bernhard Korte、 Jens Vygen)".
(latest version is sixth.)
There are some discriptions in this book that I don't understand
Not all binary ...
- 36
-1
votes
1
answer
96
views
What does the search problem imply about the decision problem?
Let $\Pi_{dec}$ be an NP-complete decision problem and let $\Pi_{opt}$ be its corresponding optimization problem. Assume $\Pi_{opt}$ can be solved in polynomial time.
What does this imply for $\Pi_{...
1
vote
1
answer
88
views
Is the problem of deciding whether two programs have the same semantics decidable?
If I have program and I want to check whether other programs have the exact same semantics or not, could I always build a machine that could make that decision?
This is a question relevant to ...
1
vote
1
answer
334
views
TM decidable or undecidable problem
Problem:
Given a TM $M$ on the alphabet $\{0,1\}$, determine if there is some input on which $M$ executes for at least 5 steps.
Is this problem decidable or not?
To check if the problem is ...
- 251
7
votes
2
answers
895
views
Are there any proofs of exponential lower bound time complexity
I'm trying to understand what are the techniques to prove an exponential time lower bound.
For some problems, we can prove that the size of the output is exponential is the size of the input, thus it ...
- 173
0
votes
2
answers
854
views
Decide whether an $n$-bit positive integer is composite
Question:
Given an $n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP?
I know that for every composite number, a factor of the number is a ...
- 3
3
votes
1
answer
237
views
Matrix element value counting in O(1) space
The question arise from my customer's real-time system (RAM model, off-course), which has very limited resources.
Given an NxM matrix of integer values, we need to verify that the number of non-zero ...
- 339
0
votes
0
answers
44
views
Confusion about P versus NP [duplicate]
I'm sure that in my following question my reasoning is extremely simplistic and flawed, but I think if someone answered this it would help me understand what the P vs NP conundrum is. So here is my ...
- 101
1
vote
1
answer
50
views
Finding f(x) using a BPP algorithm (optimization problem to decision problem)
Say there is a function $f:\mathcal{X} \mapsto \{1, 2,...,n\}$. We want to solve a specific instance of $f(x)$.
We have black box access to a BPP algorithm where it takes $T$ time to answer $\{YES, ...
- 19
1
vote
2
answers
851
views
P/NP - Polynomial Reduction vs Certificate
I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate.
How I understand polynomial reduction is that you can use it to ...
- 13
0
votes
1
answer
328
views
Decidability of decision problems
Can somebody give intuition how to answer those questions? From one side I can say that most of them are undecidable because we can reduce the halting problem to them (or halting problem can appear ...
- 3
2
votes
1
answer
210
views
BosonSampling: $\# P \subseteq FBPP^{{NP}^{\mathcal{O}}}$ implies $P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$
I am a complexity beginner, actually a quantum physicist.
In their famous BosonSampling paper, Aaronson and Arkhipov show amongst other things a polynomial time machine solving the problem of ...
- 161
2
votes
2
answers
350
views
Complement of languages and coNP
By definition, any language (decision problem) $L$ is defined as a subset of $\{0,1\}^*$, where $\{0,1\}$ is the alphabet.
$L^c$ is said to be the complement of the language, and it seems to be ...
- 217
5
votes
2
answers
2k
views
is FIND WORDS in P?
FIND WORDS is the following decision problem:
Given a list of words L and a Matrix M, are all words in L also in M?
The words in M can be written up to down, down to up, left to right, right to left,...
- 1,073
0
votes
1
answer
96
views
Descriptive complexity of 3SAT
lately I'm reading about descriptive complexity, which I find is a fascinating branch of computational complexity.
I found many formulas in $\exists$$SO$ that describe problems with graphs but none ...
- 1,073
3
votes
1
answer
4k
views
Which languages, decided by a turing machine are decidable?
How do I decide if a language is decidable and/or semi-decidable?
I have theses languages:
a) { < M > | L(M) ⊆ 0*}
b) { < M > | L(M) contains at least one word of even length}
c) {...
- 55
2
votes
1
answer
851
views
Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G
In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following:
Suppose that a friend tells you that a given
graph G is hamiltonian, and then offers to prove it by giving ...
- 229
10
votes
3
answers
4k
views
Show that there are infinitely more problems than we will ever be able to compute
I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot ...
- 1,073
1
vote
1
answer
347
views
How to determine if this problem is decidable?
I am currently stuck on the following problem:
Given a WHILE-program P and the knowledge that all input variales are set to 0, is it decidable if a specific instruction is reached 1000 times?
My ...
0
votes
1
answer
110
views
Subset with modified condition, is it still NP-complete? [closed]
So I know the conditions required for a problem to be NP-Complete is that it has to lie within NP and has to be NP-hard.
The given problem I have is subset sum.
However, the conditions have been ...
- 155
2
votes
1
answer
303
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 ...
- 29
0
votes
1
answer
230
views
NP hardness of unique Puzzle Generation
Introduction
For those who did not read my prior question, I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The ...
- 319
1
vote
1
answer
160
views
A question about decidable and undecidable problems
Maybe this question is not very smart but I really wanna learn this thing. also, I need someone who is familiar with printing 42 problem and zero program problem.
This is the context:
Consider the ...
- 125
1
vote
1
answer
224
views
3-DNF proves the algorithm is in P class
To understand fully, please read link
After, reading the link we will take a look at how we recover our solutions to a constrained Sudoku Puzzle.
If we assume that a sudoku puzzle was generated with ...
- 319