Questions related to the (computational) complexity of solving problems
5
votes
0answers
32 views
Complexity of finding a spanning tree that minimizes the maximum interference
Given $n$ nodes in the plane, connect the nodes by a spanning tree.
For each node $v$ we construct a disk centered at $v$ with radius equal to the distance to $v$’s furthest neighbor in the spanning ...
4
votes
2answers
66 views
Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$?
By a vanilla Turing machine, I mean a Turing machine with one tape (no special input or output tapes).
The problem is as follows: the tape is initially empty, other than a string of $n$ $1$s and $0$s ...
3
votes
2answers
83 views
Why is the difference of two NP-complete languages not in NP?
I found something in my notes I don't really understand, maybe you could help.
Let $A$ = Independent Set and $B$ = Clique. Then, we clearly have
$A \in \mathsf{NPC}$ and
$B \in \mathsf{NP}$.
Now, ...
8
votes
1answer
93 views
Complexity of deciding if a formula has exactly 1 satisfying assignment
The decision problem
Given a Boolean formula $\phi$, does $\phi$ have exactly one satisfying assignment?
can be seen to be in $\Delta_2$, $\mathsf{UP}$-hard and $\mathsf{coNP}$-hard. Is anything ...
7
votes
1answer
73 views
Complexity classes where $C^C = C$
One possible motivation for studying computational complexity classes is to understand the power of different kinds of computational resources (randomness, non-determinism, quantum effects, etc.). If ...
11
votes
1answer
108 views
Are 'zero-one' jigsaw puzzles NP-complete?
I'm interested in a slight variant of tiling, the 'jigsaw' puzzle: each edge of a (square) tile is labeled with a symbol from $\{1\ldots n, \bar{1}\ldots\bar{n}\}$, and two tiles can be placed ...
3
votes
1answer
33 views
Max cut in cubic graphs
The following question is related to the max cut problem in cubic graphs. In this survey paper Theorem 6.5 states
A maximal cut of a cubic graph can be computed in polynomial time
Browsing ...
2
votes
1answer
49 views
Showing a language is in co-NPC
I need to prove that this language is in co-NPC:
$\{ \langle M,x,1^n \rangle \mid M $ is a TM and for all $c \in \Sigma^*$ , $M$ accepts in $ $$n$ steps when given $(x,c)$ as input $\}$.
I tried to ...
4
votes
1answer
74 views
NP-Hardness reduction
I have a problem $\Pi_1$ that I want to show that is NP-hard. I know that I must find an NP-hard problem $\Pi_2$ and a polynomial time reduction $f()$ from instances of $\Pi_2$ to $\Pi_1$ such that ...
6
votes
1answer
73 views
Why are all problems in FPTAS also in FPT?
According to the Wikipedia article on polynomial-time approximation schemes:
All problems in FPTAS are fixed-parameter tractable.
This result surprises me - these classes seem to be totally ...
5
votes
1answer
51 views
Completeness of formal definition of 'hardness on the average'
While reading a cryptography textbook, i find the definition of a function that is hard on the average.(More precisely, it is 'hard on the average but easy with auxiliary input', but i omit latter for ...
10
votes
1answer
216 views
What is the difference between an algorithm, a language and a problem?
It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
3
votes
2answers
84 views
Polynomial-time algorithm with exponential space is eligible?
I'm curious about two things.
When we define the class called "probabilistic polynomial-time algorithm" in computer science, does it include polynomial-time algorithm with exponential space?
For ...
5
votes
4answers
82 views
Does the time complexity of a problem change with encoding of the problem?
Suppose I have a decision problem $D$ and I encode it to a language $L \subset \{0,1\}^*$. Now, I can also encode it to a different language $L'$.
Is there any theorem relating the time complexity of ...
1
vote
1answer
98 views
Problems unsolvable by an oracle machine?
Are there classes of problems that cannot be solved by an oracle machine? If so, are there specific problem examples of that class of problems?
Even the Omega number, at least the first N digits, ...
3
votes
2answers
122 views
What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$?
In these notes about quantum computation by Scott Aronson, he explains that the computation classes $\mathsf{BPP}$ is contained in $\mathsf{BQP}$, but that they are not equal, and
So, the bottom ...
7
votes
1answer
80 views
What is the complexity of the emptiness problem for 2-way DFAs?
I'm wondering, what is the time-complexity of determining emptiness for 2-way DFAs? That is, finite automata which can move backwards on their read-only input tape.
According to Wikipedia, they are ...
3
votes
1answer
55 views
Number of rounds in interactive proofs - Arora & Barak
In the web draft of Arora and Barak, "Computational Complexity: A Modern Approach", the way I understand their definition of a round of interaction is that it consists of either the verifier or the ...
2
votes
0answers
48 views
Complexity of a particular integer knapsack version
I need to know if the following problem is $NP$-complete.
The data are as follows :
$n$, number of items
$\{s_{i}\}_{i \in \{1, \dots n\}}$, item sizes, sorted by ascending values.
$S$ knapsack ...
4
votes
1answer
50 views
$\mathbf{NC}$ is closed under logspace reductions
I am trying to solve the question 6.12 in Arora-Barak (Computational Complexity: A modern approach). The question asks you to show that the
$\mathsf{PATH}$ problem (decide whether a graph $G$ has a ...
2
votes
1answer
63 views
Checking Feasibility of Linear Program in Polynomial Time
Given a linear system of the form:
$$\begin{array}{c}
x_r = a \quad x_j = b \\
c_1x_1 + c_2x_2 + \ldots + c_nx_n = N \\
x_1+x_2 + x_3 + \ldots + x_n = k\\
0 \le a,b,x_1,x_2,x_3...x_n \le 1\\
k \ge 0
...
2
votes
1answer
47 views
BPP upper bound
does $BPP\subseteq P^{NP}$ ? it seems reasonable but I don't know if there is a proof of this!could any one post a proof or any material that discusses the statement or something that look like this . ...
5
votes
1answer
73 views
Interactive Proofs for coNP
I am trying to understand interactive proof systems and tried the following problem as an exercise. We know that $PH \subseteq PSPACE$ and $IP=PSPACE$, so come up with (easy to understand) interactive ...
4
votes
2answers
115 views
Example for a non-trivial PCP verifier for an NP-complete problem
During my involvement in a course on dealing with NP-hard problems I have encountered the PCP theorem, stating
$\qquad\displaystyle \mathsf{NP} = \mathsf{PCP}(\log n, 1)$.
I understand the ...
6
votes
2answers
270 views
Decision problems in $\mathsf{P}$ without fast algorithms
What are some examples of difficult decision problems that can be solved in polynomial time? I'm looking for problems for which the optimal algorithm is "slow", or problems for which the fastest known ...
3
votes
1answer
76 views
Is this NP-hard: min-weight n-clique in a complete n-partite graph
I have a complete $n$-partite graph, where each partite set has $n$ vertices (yes it's also $n$), so the graph has $n^2$ vertices in total. My problem is to find a minimum weight $n$-clique in the ...
2
votes
1answer
118 views
Do I understand pseudo polynomial time correctly?
The running time of knapsack is $O(n*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time ...
0
votes
1answer
42 views
3 Colorability reduction to SAT
I'd like to reduce 3 colorability to SAT. I've stuffed up somewhere because I've shown it's equivalent to 2 SAT.
Given some graph $G = (V,E)$ and three colors, red, blue, green. For every vertex $i$, ...
4
votes
1answer
41 views
Partition problem with distinct integers
Partition problem is a well known NP-complete problem. In the definitions I have seen, the input is assumed to be a multiset of integers and we want to decide the existance of a partition into two ...
3
votes
1answer
112 views
Can we read N numbers in O(N) time?
In a different post it came up that
(using the Turing machine model of computation),
it is not even safe to say that $N$ numbers can be read in $O(N)$ time.
To me this is boggling since
it's ...
1
vote
2answers
58 views
How to show that problems are in NP?
I want to show that the following problems are in NP (NP-completeness is irrelevant) by textually describing a non-deterministic Turing machine which runs in polynomial time. The assumptions are that ...
5
votes
1answer
68 views
Proving that a language is not in P using diagonalization
Pardon me if i'm missing something which is very obvious here but i cant seem to figure it out.
$E=\{ \langle M, w \rangle \mid \text{ Turing Machine encoded by $M$ accepts input $w$ after at most $ ...
1
vote
1answer
64 views
Connection CSP and 3SAT
I am interested in showing connection between CSP (Constraint Satisfaction Problems) as it's defined in CSP (definition with Constraint graph, sometimes called binary CSP) and 3SAT problem, when ...
3
votes
1answer
58 views
Checking whether a directed graph on n vertices contains exactly 10*sqrt(n) strongly connected components is in non-deterministic logspace
I am studying now for a test in my complexity course. When I solved previous exams I saw the following question : Prove that the language $L$ of all directed graphs on $n$ vertices that contain ...
5
votes
1answer
52 views
How hard is finding restricted assignment of 3-SAT satisfying $7/8$ of the clauses?
The PCP theorem implies (with other results) that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = ...
7
votes
2answers
109 views
Quantum computers, parallel computing and exponential time
I've read that quantum computers can solve 'certain problems' exponentially better than classical computers. As I think I understand it, it's NOT the same to say that quantum computers take any ...
-1
votes
1answer
33 views
Properties of polynomial time many-one reductions
I'm working on old multiple choice exams and would like to know if the following statements are true or false:
a) $L_1 \le_p L_2 \le_p L_3 \Rightarrow L_1 \le_p L_3$
b) If $L \in \mathsf{NP}$ and $U ...
2
votes
1answer
27 views
PCP deterministic emulation
Suppose that $S \in PCP(r(n),q(n))$, colclude that $S \in NTIME(2^r \cdot poly) \cap DTIME(2^{2^r q+r} \cdot poly)$
The idea of a nondeterminstic simulation of the $V$ on input $x$ is simple, guess a ...
3
votes
0answers
30 views
Existence of Hamiltonian cycle in a 3-regular $C_n$-free graph
I know that Hamiltonian cycle problem in 3-regular triangle-free graphs is NP-complete. I would like to know how far we can stretch this result. Observing that a triangle is just $C_3$ cycle, What is ...
8
votes
5answers
361 views
How to prove a problem is NOT NP-Complete?
Is there any general technique for proving a problem NOT being NP-Complete?
I got this question on the exam that asked me to show whether some problem (see below) is NP-Complete. I could not think of ...
3
votes
1answer
41 views
Why/how does the definition of PCP use randomness?
I am confused by the definition of probabilistic checkable proofs.
Language $L$ has an $(r(n),q(n))$ - PCP verifier, if there is a PPA V satisfying:
Efficiency: $V$ uses at most $r(n)$ random coins ...
4
votes
1answer
102 views
Find which vertices to delete from graph to get smallest largest component
Given a graph $G = (V, E)$, find $k$ vertices $\{v^*_1,\dots,v^*_k\}$, which removal would result in a graph with smallest largest component.
I assume for large $n = |V|$ and large $k$ the problem ...
1
vote
0answers
23 views
Is this problem in P: Finding a common key for a collection of systems of equations?
Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all ...
-1
votes
8answers
366 views
What are the minimalist NP-complete problems in mathematics? [closed]
This is inspired by this MathOverflow problem, What are the most attractive Turing undecidable problems in mathematics?
What are the minimalist NP-complete problems in mathematics?
I will accept ...
2
votes
1answer
40 views
Space(n) not closed under Karp reductions - what about NTime(n)?
In the book on complexity by Arora and Barak, there is an exercise to show $Space(n)\neq NP$, the proof of which goes by showing that $NP$ is closed under Karp reductions, while $Space(n)$ isn't.
To ...
6
votes
4answers
166 views
Why is NFA minimization a hard problem when DFA minimization is not?
I know that we can minimize DFAs by finding and merging equivalent states, but why can't we do the same with NFAs? I'm not looking for a proof or anything like that--unless a proof is simpler to ...
2
votes
1answer
48 views
Is the following langauge in $P$ or $NPC$
Assuming $P \neq NP$ Is the following langauge in $P$ or $NPC$:
$L=\{\langle\phi\rangle\mid\phi$ is a 3CNF formula with an assignment satisfying at least half of the clauses$\}$
The first thing I ...
3
votes
1answer
34 views
Where can i find literature about the $\frac{4}{3}$-conjecture for approximation of the Metric TSP?
In Graph-Theory there are many ways for efficient approximation-algorithms to solve the Metric TSP. The best solution seems to be the Christofides Heuristic with a factor of 1.5 to the optimal ...
9
votes
1answer
94 views
Use minimum number of swaps so each bin contains balls of the same color
There are $n$ bins, the $i$th bin contain $a_i$ balls. The balls has $n$ colors, there are $a_i$ balls of color $i$. Let $m=\sum_{i=1}^n a_i$.
A swap is take a ball from one bin and swap with a ball ...
1
vote
2answers
90 views
Why NP is not closed under Turing reduction
The notion of polynomial time Turing reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using another algorithm as a subroutine.
For ...
