The polynomial-time tag has no wiki summary.
2
votes
2answers
44 views
What is a Turing Machine in class coNP
On the wikipedia article about the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy
it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A ...
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
1answer
37 views
Exponential reduction vs Polynomial Reduction
I'm having trouble understanding reduction. Lets say you have a decision problem A that is NP-Complete. Also, another problem B the can be reduced from A.
What can you say about B if:
1) The ...
1
vote
1answer
39 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$ ...
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
votes
1answer
38 views
Reducing from Hamiltonian Cycle problem to the Graph Wheel problem cannot be proved vice versa [closed]
I saw a proof by Saeed Amiri,
We will add one extra vertex v to the graph G and we make new graph G′, such that v is connected to the all other vertices of G. G has a Hamiltonian cycle if and only if ...
0
votes
2answers
152 views
P is contained in NP ∩ Co-NP?
How should I show that ${\sf P}$ is contained in ${\sf NP} \cap {\sf CoNP}$?
I.e., all polynomial time solvable problems and their complements are verifiable in polynomial time.
2
votes
1answer
26 views
Can you convert a positively weighted DAG into a non-weighted DAG in polynomial time?
Given a positively weighted DAG (directed acyclic graph) $D = (V,E)$, can you create a new non-weighted DAG $D'$ by converting each edge with weight $w(e) = x$ into x non-weighted edges and vertices? ...
5
votes
2answers
163 views
Finding shortest and longest paths between two vertices in a DAG
Given an unweighted DAG (directed acyclic graph) $D = (V,A)$ and two vertices $s$ and $t$, is it possible to find the shortest and longest path from $s$ to $t$ in polynomial time? Path lengths are ...
3
votes
2answers
78 views
If A is poly-time reducible to B, is B poly-time reducible to A?
Basically, is the following statement true?
$A \leq_p B$ $\rightarrow$ $B \leq_p A$
0
votes
1answer
43 views
How to check whether a graph is connected in polynomial time?
I have to solve the following problem:
Consider the problem Connected:
Input: An unweighted, undirected graph $G$.
Output: True if and only if $G$ is connected.
Show that Connected ...
2
votes
2answers
60 views
Why does a polynomial-time language have a polynomial-sized circuit?
I wish to understand why P is a subset of PSCPACE, that is why a polynomial-time langauge does have a polynomial-sized circuit. I read many proofs like this one here on page 2-3, but all the proofs ...
2
votes
2answers
82 views
The exact relation between complexity classes and algorithm complexities [duplicate]
Are all algorithms which have polynomial time complexity belong to P class ? And P class do not have any algorithm which does have not polynomial complexity ?
Are all algorithms which have non ...
3
votes
1answer
102 views
Propositional formula in DNF can be decided in polynomial time?
For a given propositional formula f in DNF, one can decide in polynomial time, if the formula is satisfiable:
Just walk through all subformulas (l_1 and ... and l_k) and check, wheter it has NO ...
-2
votes
1answer
113 views
Exponential input and poly-time algorithm
For a list of integers, of size n, where n is exponential, will merge-sort(n), run in poly-time or psuedo poly-time?
3
votes
1answer
89 views
Polynomially related lengths under two different encodings
I'm reading through "Computers and Intractability: A guide to the Theory of NP-Completeness" by Michael R. Garey and David S. Johnson, p. 20 and I came across this ...
7
votes
1answer
113 views
Find small superset of at least k of n given sets
Say we're given $n$ sets and the size of their union is $m$. We would like to construct a small set which contains at least $k$ of the $n$ given sets.
Lets assume that $m$ is less than some ...
1
vote
1answer
81 views
Problem with the definition of P
In "Introduction to Algorithms: 3rd Edition" there is Theorem 34.2, which states
$P = \{ L \mid L \text{ is accepted by a polynomial-time algorithm} \}$
"Accepted in polynomial-time" is defined ...
6
votes
2answers
158 views
Is SAT in P if there are exponentially many clauses in the number of variables?
I define a long CNF to contain at least $2^\frac{n}{2}$ clauses, where $n$ is the number of its variables. Let $\text{Long-SAT}=\{\phi: \phi$ is a satisfiable long CNF formula$\}$.
I'd like to know ...
