Questions related to the (computational) complexity of solving problems
3
votes
1answer
44 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
35 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 ...
4
votes
1answer
48 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
61 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
45 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
37 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
63 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
29 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 ...
1
vote
1answer
25 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
24 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
316 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
39 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
52 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
22 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 ...
0
votes
8answers
285 views
What are the most natural NP-complete problems in mathematics?
This is inspired by this MathOverflow problem, What are the most attractive Turing undecidable problems in mathematics?
What are the most natural (elegant) NP-complete problems in mathematics?
I ...
2
votes
1answer
32 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
134 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
40 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
33 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
81 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
69 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 ...
11
votes
1answer
71 views
Are runtime bounds decidable for anything nontrivial?
Problem Given a Turing machine $M$ which has known runtime ${O}(g(n))$ with respect to input length $n$, is the runtime of $M \in {O}(f(n))$?
Is the above problem decidable for some ...
5
votes
1answer
45 views
Minimal positive difference of a mulitset of real numbers
Motivated by Max-Flow: Detect if a given edge is found in some Min-Cut, I'd like to ask the following questions:
Given a multiset of real numbers $B$, how hard is it to compute the minimal positive ...
2
votes
0answers
46 views
Coordinated Attack Problem On The Arbitrary Graph
Let consider a general version of Two Generals' Problem, when there are $n$ generals located on the arbitrary graph and they should agree on exactly the same value whether to attack or not to attack. ...
0
votes
0answers
27 views
Nash Equilibrium in Tree of Bounded Degree
I have an exercise which I can't solve.
Exercise. Consider a game where the players have $2$ pure strategies each and assume that the graph $G$ is a tree with maximum degree $3$. Give a polynomial ...
0
votes
0answers
30 views
Search space complexity of directional semantic network
How can I compute the search space complexity of a directional semantic network (i.e. a network where each semantics consist of two nodes and a directional link stands for their semantic relation)?
...
1
vote
0answers
16 views
Name and complexity of a problem concerning metrics
Do you know the name of the following problem and can you give a reference for its complexity (especially the relation to $\mathsf{GraphIsomorphism}$ and/or other isomorphism/homomorphism problems)?
...
4
votes
0answers
38 views
'Stones' game complexity
I'm trying to find complexity class of finding winning strategy for first player in following game:
Intance of 'Stones' game is:
finite set $X$
relation $R \subseteq X^3$
set $Y \subseteq X$ and ...
1
vote
1answer
41 views
Traveling salesman problem - negative distances allowed
I am interested in the following version of TSP:
Assumption: TSP where the distances are non-negative. We know the algorithm A which computes the optional solution for such instances of TSP.
Task: ...
3
votes
1answer
53 views
Is np-complete an equivalence class?
So, there are multiple possible definitions of "np-complete", two of which being:
A decision problem $L$ is np-complete if and only if: $L \in \text{NP}$ and $\forall L' \in \text{NP}: L' ...
1
vote
1answer
40 views
Prove that if a problem L can be decided in polynomial time, then L ≤p L' for any other problem L'
So we know that there exists a Turing Machine $M$ and a polynomial $T$ such that:
$M$ halts on all inputs within at most $T(|x|)$ steps
If $x$ is in $L$ then $M$ accepts $x$
If $x$ is not in $L$ ...
4
votes
1answer
75 views
Assuming NP $\neq$ P, are there NPI languages only P languages reduce to?
let $L_c$ be the class of all languages that have a polynomial reduction to some language L, for example if $L=SAT$ then $SAT_c=NP$.
Assuming know that $NP\neq P$ we know that there exist languages ...
2
votes
1answer
50 views
$\mathsf{RegExpEq_*} \in \mathsf{coNPC}$ but why isn't in $\mathsf{P}$
Hello for a homework I have to show that deciding whether a regex over $\Sigma = \{0,1\}$ descibes $\Sigma^*$ is $\mathsf{coNP}$ complete (this is irrelevant for the question though).
The thing which ...
-3
votes
2answers
60 views
Does reachability belong to P?
Reachability is defined as follows:
a digraph $G = (V, E)$ and two vertices $v,w \in V$. Is there a directed path from $v$ to $w$ in $G$?
Is it possible to write a polynomial time algorithm for it?
...
2
votes
0answers
43 views
Hardness of a special case of maximum matching
Input: A set of $n$ Users $U=\{u_1, ..., u_n\}$ and a set of $m$ products $I=\{i_1, ..., i_m\}$. Associated with each pair $u \in U$ and $i \in I$ is the probability $p_{u,i}$ of $u$ purchasing ...
1
vote
0answers
23 views
NOELEMENTARY complexity class [closed]
I was reading on Wikipedia about the NOELEMENTARY complexity class. However, googling the problems listed I could not find anything about them. Could someone give me a reference about this class?
4
votes
1answer
83 views
Longest path in grid like graph
This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:
Find the length of the longest ...
2
votes
1answer
40 views
Complexity of $Ax\geq 0$
May be it's a stupid question (sorry if it's the case).
What is the complexity the decision problem:
Input: $A\in\mathcal{M}_{n,m}(\mathbb{Z})$
does there exists $x\in\mathbb{N}^n,x>0$ such that ...
2
votes
1answer
23 views
Showing filling a container with rectangles is hard by reducing from SUBSET-SUM
Given a set of rectangles, $D = \{ (a_1, b_1), (a_2, b_2) \dots , (a_n, b_n) \}$, where in each pair $(a_i, b_i)$, $a_i$ represents the height of the rectangle and $b_i$ the width, and given another ...
1
vote
1answer
33 views
Is there a program to solve a metric TSP for 80 edges at optimum?
i'm going to use the Christofides heuristic algorithm in order to solve a TSP for about 80 edges. Eventually i should have a solution, that is within the factor 1.5 of the optimum.
But when i'm ...
0
votes
1answer
75 views
Proving that if coNP $\neq$ NP then P $\neq$ NP
I am new in complexity theory and this question is a part of a homework that I have and I am stuck on it.
Let ${\sf coNP}$ be the class of languages $\{\overline{L}: L \in {\sf NP} \}$.
Show ...
4
votes
1answer
32 views
$\mathsf{2EXP} = \mathsf{EXP}^{\mathsf{EXP}}$?
It is clear that any language in $\mathsf{EXP}^{\mathsf{EXP}}$ can be computed in $\mathsf{2EXP} = \mathsf{DTime}(2^{2^{\mathsf{poly}(n)}})$.
My question is whether the converse is true: is ...
1
vote
1answer
60 views
If A many-one reduces to B, does the complement of A many-one reduce to the complement of B?
If A many-one reduces to B, does the complement of A many-one reduce to the complement of B? My gut says no but I am having a hard time finding a counterexample.
1
vote
1answer
47 views
Using software to calculate the complexity of an algorithm
I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some ...
3
votes
2answers
138 views
Modeling the problem of finding all stable sets of an argumentation framework as SAT
As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form.
Problem: Find all stable sets ...
3
votes
1answer
36 views
Are there any problems in $APX - PTAS$ that are not $APX$-complete?
I have a question about the structure of the complexity class $APX$. Obviously, unless $P=NP$, no problem in the class $PTAS$ can be $APX$-complete (under the AP-reduction). However, what about the ...
1
vote
0answers
35 views
Start using SAT Solvers [duplicate]
What i actually want to do is to turn a math problem ,i have to solve,to a Boolean Satisfiability problem and solve it using a SAT Solver.
I wonder if someone knows any manual,guide or anything that ...
3
votes
2answers
87 views
Please explain “decidability” and “verifiability”
I am trying to (intuitively) understand the two terms "decidability" and "verifiability".
I have done a reasonable amount of searching and going through the various texts I can put my hands on. ...
7
votes
0answers
163 views
Google Code Jam Great Wall Problem
So, Google Code Jam round 1C has just wrapped up, and one of its problems seems rather elusive to me: https://code.google.com/codejam/contest/2437488/dashboard#s=p2
A quick summary of the problem is ...
6
votes
0answers
100 views
$NEXP = \Sigma_2 \implies NEXP = MA$?
Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds?
(The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} ...
