A question in some formal system with a yes-or-no answer.
8
votes
0answers
141 views
+50
Longest cycle contained in two cycles
Is the following problem NP-complete? (I assume yes).
Input: $k \in \mathbb{N},G=(V,E)$ an undirected graph where the edge set can be decomposed into two edge-disjoint simple cycles (these are not ...
5
votes
1answer
98 views
NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?
I have seen some problems that are NP-hard but polynomially solvable in fixed dimension.
Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer ...
2
votes
0answers
39 views
Decision vs Optimization version for Problems of two Parameters
Let's say I have an optimization problem called $k$-foo which asks for a solution of size $k$ minimizing some quality criterion.
Now the corresponding decision problem $foo(M)$ would be: Is there a ...
0
votes
1answer
46 views
Algorithm to determine if a number is perfect on a Turing Machine
I've been trying for a while now to find a solution for the problem in the title: determining if a number is perfect using a Turing Machine. I only had one class on the TM and while I did "get" how it ...
3
votes
1answer
83 views
How does the problem of having a coffee-machine close relate to vertex cover?
Meeting rooms on university campuses may or may not contain coffee machines. We would
like to ensure that every meeting room either has a coffee machine or is close enough to a
meeting room ...
2
votes
1answer
35 views
Is the 0-1 Knapsack problem where value equals weight NP-complete?
I have a problem which I suspect is NP-complete. It is easy to prove that it is NP. My current train of thought revolves around using a reduction from knapsack but it would result in instances of ...
3
votes
1answer
141 views
Do any decision problems exist outside NP and NP-Hard?
This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard.
In order to be in NP, problems have to have a ...
2
votes
1answer
95 views
Is every regular language Turing-decidable, and how can we prove this?
I know every regular language is Turing-acceptable, but does that imply it is Turing-decidable?
1
vote
2answers
75 views
Polynomial time reductions using binary search
There are many NP-complete decision problems that ask the question whether it holds for the optimal value that OPT=m (say bin packing asking whether all items of given sizes can fit into m bins of a ...
6
votes
3answers
159 views
Is there a efficient test for if an NFA accepts a subset of another NFA?
So, I know that testing if a regular language $R$ is a subset of regular language $S$ is decidable, since we can convert them both to DFAs, compute $S \cap \bar{R} $, then test if this language is ...
2
votes
0answers
39 views
Travelling salesman problem with detours
I am interested if there exists a following version of the travelling salesman problem:
INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each ...
3
votes
1answer
36 views
Is matching with mismatches a special(parametrized) case of Closest String problem?
I am a bit confused. Somehow I have a problem connecting two problems together. The Closest String problem and the problem of matching with mismatches. They seam to be related but, I fail to see the ...
2
votes
3answers
147 views
What is the decision version of independent set?
I always read that finding an independent set of size $k$ in a graph is $\mathsf{NP}$-complete. However, this only requires looking for all combinations of $k$ vertices and this is a polynomial ...
8
votes
4answers
195 views
Is it possible to decide if a given algorithm is asymptotically optimal?
Is there an algorithm for the following problem:
Given a Turing machine $M_1$ that decides a language $L$,
Is there a Turing machine $M_2$ deciding $L$ such that
$t_2(n) = o(t_1(n))$?
The ...
5
votes
1answer
92 views
Complexity of a subset sum variant
Is this variant of the subset sum problem easy/known?
Given an integer $m$, and a set of positive integers $A = \{x_1, x_2, ..., x_n\}$ such that every $x_i$ has at most $k=2$ bits set to $1$ ($x_i ...
2
votes
1answer
62 views
Decision problem and algorithm
I was reading about decision problem. I understand that decision problem tell yes/no answer for an input. The decision is based on a decision procedure also called an algorithm.
The wikipedia says ...
0
votes
1answer
116 views
Solving algorithmic problems
Is the first step in solving a "tough" algorithmic problem always asking whether it's hard in the sense that other tough problems can be reduced to it? Not to make the scope of this question tight, ...
1
vote
1answer
140 views
Is the intersection of two regular languages regular?
Trivially decidable problem is one in which the problem is a known property of the language/grammar. So intersection of two regular languages is regular should be trivially decidable? But it is given ...
4
votes
1answer
114 views
NP-Hard problems which are not NP-Complete
Is it always true that a problem which is ${\sf NP}$-hard but not ${\sf NP}$-complete is an optimization problem such as Minimum-Vertex-Cover and many others.
Is it always true that a ${\sf ...
0
votes
1answer
88 views
Shifting subset sum solution by constant positive integer
While reading the Wikipedia article about the subset sum problem I came across this example: "is there a non-empty subset whose sum is zero? For example, given the set $\{ −7, −3, −2, 5, 8 \}$, the ...
3
votes
1answer
77 views
Complement of HAMPATH
Is the complement of the Hamiltonian Path problem known to be in $\mathsf{NP}$? I could not find explanations saying that it is, but then neither were there any claims saying that it is not in ...
2
votes
1answer
224 views
Given a truth table, force a contradiction
Suppose I have a formula, and a lying witness is attempting to make it evaluate to False.
Given a truth table $c(F_1,…, F_n)$, how could you force a lying
witness to contradict herself?
A ...
5
votes
1answer
82 views
Is the validity of some instance of an equational problem decidable?
Is the following FOL-problem (equality is a logical symbol)
effectively decidable?
Given. A finite equation system $E$ and an equation $s = t$.
Question. Is there a substitution $\sigma$, such ...
2
votes
1answer
203 views
Optimization problem vs decision problem - reduction
Assume we have an optimization problem with function $f$ to maximize.
Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
3
votes
1answer
201 views
Examples of undecidable problems whose intersection is decidable
I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the ...
3
votes
2answers
66 views
Kolmogorov complexity of a decision problem
What's the definition of Kolmogorov complexity for a decision problem? For example, how to define the length of the shortest program that solves the 3SAT problem? Is it the "smallest" Turing machine ...
4
votes
1answer
151 views
What complexity class does this variation of traveling salesman problem belong to?
Given a TSP instance $T$, decide whether changing the city coordinates by adding a vector of coordinates $v$ will change the optimal TSP objective by atleast $x$. The city coordinates are integers.
...
10
votes
2answers
107 views
An $\mathbb F$-algebra as input to an algorithm
I want to specify, what it means to give an algebra as input to an algorithm and didn't find very much literature about it. So first I want to ask if you can recommend a book or paper that deals with ...
7
votes
3answers
595 views
Why isn't this undecidable problem in NP?
Clearly there aren't any undecidable problems in NP (if there were, we'd know, for example, that P != NP). However, according to Wikipedia:
NP is the set of all decision problems for which the ...
9
votes
2answers
146 views
What is the difference between “Decision” and “Verification” in complexity theory?
In Michael Sipser's Theory of Computation on page 270 he writes:
P = the class of languages for which membership can be decided quickly.
NP = the class of languages for which membership can be ...
9
votes
2answers
491 views
Optimization version of decision problems
It is known that each optimization/search problem has an equivalent decision problem. For example the shortest path problem
optimization/search version:
Given an undirected unweighted graph ...
4
votes
2answers
279 views
All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?
My book states this
If a decision problem B is in P and
A reduces to B,
then decision problem A is in P.
A decision problem B is NP-complete if
B is in NP and
for every problem in A ...
