The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
4answers
437 views

How can an algorithm have exponential space complexity but polynomial time complexity?

For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm "GENERATE-MFVS" in their publication "On enumerating all minimal solutions of feedback ...
2
votes
1answer
33 views

Proof of P-Hardness by reduction

I want to proof the P-Hardness of a language. Why is it enough to make a reduction-proof from an other, already P-Complete known language?
4
votes
1answer
44 views

Understanding the Sipser-Gacs-Lautemann theorem

The class $BPP$ contains all the languages decided by a probabilistic Turing machine in polynomial time with probability of success more that 2/3 for every input. The class $\Sigma^p_2$ contains all ...
2
votes
1answer
36 views

Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?

According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved ...
3
votes
0answers
24 views

Finding a perfect matching using an LP

I have a basic question about the power of Linear Programming that has been bothering me for some time. I believe there is something simple I am missing. Linear Programming is $\mathsf{P}$-complete, ...
4
votes
1answer
88 views

Complexity of Linear Diophantine equations

My question is simply, can linear Diophantine equations be solved in polynomial time? Specifically, I am looking at equations of the form $a_1 x_1+a_2 x_2 + ... + a_n x_n = k$, where $a_i,x_i,k$ are ...
4
votes
1answer
130 views

Complexity of the decision version of determining a min-cut

I was wondering what the complexity of the following problem is: Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$. Question: Is there an $s$-$t$ cut of capacity at most ...
3
votes
1answer
62 views

A Reduction from XORSAT to 2-SAT

Does anyone know of a non-trivial reduction from XORSAT to 2-sat since they are both in P? (By non-trivial I mean one that does not just solve the instance of XORSAT and map it to a fixed instance of ...
3
votes
1answer
82 views

Finding number not in list with wildcards

I have a list like this: 1*0*0 1**0* 0*0** 001** Where the number of elements in each row is $n$ and * is a wildcard for 0 or 1. I need a polynomial-time ...
4
votes
1answer
74 views

Unary in $P$, binary not in $P$

I would like to know if there is a known decision problem with the following characteristics: Represented in unary, the problem is decidable in polynomial time. Represented in binary, the problem is ...
-1
votes
1answer
41 views

Is P^SAT subset of sum of NP and co-NP

I have a following problem: Let $P^{SAT}$ be a class of problems decidable by a deterministic polynomial Turing Machines with SAT oracle. (only one question to oracle). Assume that: $co-NP \neq NP ...
5
votes
0answers
63 views

A matrix rank problem over finite fields

I have already asked a similar question here, but since I have not got an acceptable answer, I decided to ask a simpler version of the question here. Let $M|\mathbf w$, where $M$ is a matrix and ...
3
votes
4answers
899 views

How to prove that problem is not in P

Given some abstract problem how can I prove that this problem is not in P. I mean, what is the method for proving such thesis?
2
votes
1answer
35 views

A variant of the set cover problem: Is that a known problem?

Can this problem be solved in poly time? Input: $S_i \subset \{1,\cdots,n\}$ for $i=1,\cdots, n$. Question: Is it possible to select an $a_i \in S_i$ for each $i=1,\cdots,n$, such that ...
1
vote
3answers
73 views

NP-completeness: Reduce to or reduce from?

Very simple question, but a mistake I make often enough that I'd love to have a standard reference. I'm showing that a problem $P$ is NP-Hard by assuming I have a polynomial time algorithm to solve ...
3
votes
3answers
334 views

Can't understand why the DP Subset Sum algorithm is not polynomial

I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial. Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the ...
0
votes
1answer
41 views

Is polynomial time reducibility reversible?

If a language $A$ is reducible to some language $B$, does it follow that $B$ is reducible to $A$? My guess is no, it having something to do with the function $f$ in the definition of $A$ reducing to ...
0
votes
1answer
35 views

Complexity of general polynomial map evaluation is polynomial?

A polynomial map is equal to another polynomial map iff they take on the same values at each point. So this is different from formal polynomials. So since in $\Bbb{Z}_p$, $x^{p-1} = 1$ for all $x ...
3
votes
2answers
296 views

How to determine if a black-box is polynomial or exponential

I have a problem which essentially reduces to this: You have a black-box function that accepts inputs of length $n$. You can measure the amount of time the function takes to return the answer, but ...
2
votes
1answer
58 views

How to optimally seperate a student body?

Students will identify certain students they want to work with. I have therefore decided to split them into two groups where I want to minimize the number of people in Group 1 who want to work with ...
2
votes
1answer
29 views

Polynomial hierarchy intersection

While familiarizing myself with polynomial hierarchy, I have come across a problem of showing $NP^{\Sigma_{k}^{p} \cap \Pi_{k}^{p}} \subseteq \Sigma_{k}^{p}$. By looking at the proof for $NP^{SAT} ...
2
votes
1answer
39 views

Polynomial Hierarchy — polynomial time TM

Consider, for example, the definition for $\Sigma_2^p$ complexity class. $$ x \in L \Leftrightarrow \exists u_1 \forall u_2 \;M(x, u_1, u_2) = 1, $$ where $u_1, u_2 \in \{0,1\}^{p(|x|)}$, for some ...
1
vote
1answer
33 views

Is P closed under subwords? [closed]

Given a language $L\subseteq \Sigma^*$ in $P$, is the language $subwords(L) = \{v\in\Sigma^* : \text{there exist } u,w\in \Sigma^* \text{ with } uvw\in L\}$ that consists of all subwords of words ...
1
vote
1answer
81 views

Relation between logspace-uniform circuits and P-uniform circuits

In the book "Computational complexity" of Barak and Arora, on page 112, they state that: Theorem 6.15: A language has logspace-uniform circuits of polynomial size iff it is in P. The proof of ...
0
votes
1answer
60 views

What's the difference between “polynomial time Turing-reducible” and “polynomial time many-to-one reducible”? [duplicate]

The following definitions are from Li, M., & Vitányi, P. (1997). An introduction to Kolmogorov complexity and its applications (2nd ed.), pg. 38. A language $A$ is called polynomial time ...
0
votes
1answer
115 views

Does two languages being in P imply reduction to each other?

Given two languages $L_1$ and $L_2$ that are in $\mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how? I noticed that if $L_1$ is the ...
1
vote
2answers
156 views

P vs NP: Assuming P = NP

Lets assume $P = NP$. Can we say if every language $L \in P$, then $L \in NPC$? I read $P \subseteq NP$, which means that $L\in NP$. So I know for example, that a language can be $NP \text{ hard}$, ...
1
vote
1answer
194 views

how to solve NFA acceptance problem in polynomial time

I need to show that the language Anfa = {(A,w)| A is an nondeterministic finite automata that accepts w} can be decided in polynomial time. My problem is every solution that I think of requires ...
7
votes
4answers
170 views

Problems that are NP but polynomial on graphs of bounded treewidth

I heard here that the Hamiltonian cycle problem is polynomial on graphs of bounded treewidth. I am interested in examples/references to different problems which is essentially hard but having ...
1
vote
1answer
390 views

Is the set partitioning problem NP complete?

I know that the set partitioning problem defined like this: Given $S = \left\{ x_1, \ldots x_n \right\}$, find $S_1$ and $S_2$ such that $S_1 \cap S_2 = \emptyset$, $S_1 \cup S_2 = S$ and $\sum_{x_i ...
2
votes
1answer
112 views

Time complexity of languages that are polynomial time reducible to NP complete languages

I am wondering if given the time complexity of an NP-Complete problem or at least some information about it for example if $ SAT\in Time(2^{sqrt(n)})$ (hypothetically) could I assume that all ...
3
votes
1answer
195 views

Is the set-partition problem polynomial time reducible to the subset-sum problem?

There are many solutions on the web showing that the subset-sum problem is polynomial time reducible to the set-partition problem. However, during my search, I came across the following powerpoint ...
-1
votes
1answer
291 views

Proving that the complexity class $P$ is closed under union

The following is my proof for $P$ being closed under union. I wish to know if my proof is correct in addition to what it means for the union of two problems. Proof: Let $p_1, p_2 \in P$ Then by ...
0
votes
0answers
134 views

Proving languages are complete on NL?

I'm trying to prove that every language that is not the empty set or {0,1}* is complete for NL (nondeterministic logarithmic space) under polynomial-time Karp reductions. I'm really not sure how to ...
2
votes
1answer
196 views

Is it possible to solve parity game problem in polynomial time?

Is it practically possible or even near possible to make parity game to be solved in polynomial time? If yes, how? and if No, why?
-2
votes
1answer
93 views

Deterministic Random access machine and polynomial time

How do we prove $M$ that is a deterministic random access machine that decides a problem $A$ for an input $i$, and $u_M(i)$ is the set of addresses of those registers that occur at least once with $s$ ...
4
votes
2answers
215 views

Why do most scientists believe that P≠NP?

I read that most scientist don't believe that P=NP. This might be subjective but can you simplify why not? I'm not informed enough to have an opinion but I'd like to know the definitions and some ...
3
votes
2answers
238 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
2answers
283 views

What exactly is polynomial time?

I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not ...
5
votes
1answer
113 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
votes
1answer
96 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
0answers
30 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 ...
3
votes
2answers
94 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
48 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
81 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
131 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
43 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
133 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
214 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
42 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? ...