Questions tagged [polynomial-time]

Use for algorithms, algorithm-analysis and complexity-theory questions that aim for polynomial running time resp. time complexity. Such questions often are are reference-requests or about runtime-analysis or time-complexity.

Filter by
Sorted by
Tagged with
4
votes
4answers
5k 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?
4
votes
2answers
547 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 ...
4
votes
2answers
293 views

“P may collapse” vs. Time hierarchy theorem

https://en.wikipedia.org/wiki/P_versus_NP_problem states: If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level. They further state that this may be ...
4
votes
4answers
5k views

Show that P is closed against the Kleene star

I have that question that looks kinda easy at first but it is quite hard. Let $L\in P$. Prove that $L^*\in P$ my approach: I tried to generate a Turing machine but I got stuck with the thing of ...
4
votes
2answers
204 views

Where/how did a $\log(n)$ factor disappear from well-known algorithms?

Consider the binary search problem on a sorted array containing $n$ integers on 16 bits. Everybody agrees that the binary search needs $O(\log(n))$ time, because it makes at worst $O(\log(n))$ steps. ...
4
votes
2answers
444 views

What are the examples of problems which first had large polynomial time complexity algorithms but later the complexity was reduced significantly?

Arora-Barak says It has also happened a few times that the first polynomial-time algorithm for a problem had high complexity, say $n^{20}$, but soon somebody simplified it to say an $n^5$ time ...
4
votes
3answers
1k views

What is difference between nondeterministic polynomial time and exponential time?

I am not very into computer science theory but i feel like people are defining nondeterministic polynomial time as if it is another name of exponential time. I would be happy if you clarify it. thank ...
4
votes
3answers
77 views

What is the difference between saying there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time and $n^{2-o(1)}$ or $\Omega(n^2)$?

I have seen the formulations there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time a problem requires time $n^{2-o(1)}$ a problem requires time $\Omega(n^2)$ being used ...
4
votes
1answer
1k views

Minimum diameter spanning tree problem

Minimum diameter spanning tree (MDST) problem is defined as following: given the connected weighted graph $G(V, E)$, weight function $w: E \rightarrow R, w(e) > 0\ \forall e \in E$, find the ...
4
votes
2answers
3k views

Can the isomorphic graph problem be solved in deterministic polynomial time?

Here is a recent homework problem of mine: Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic graphs}. Show ...
4
votes
1answer
228 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 ...
4
votes
2answers
483 views

Computationally 'hard' polynomial-time reduction to other NP-complete problems / Hierarchy of NP-complete problems

As we all know there exist plenty of polynomial-time reductions from one NP-complete problem to another. Are there any NP-complete problems that have a rather large polynomial bound for reductions to ...
4
votes
1answer
152 views

Is every language in PTime also context-sensitive?

Context-sensitive languages are exactly those that can be recognised using linearly bounded automata, i.e., those in NSPACE(O($n$)). This subsumes all languages that can be recognised in linear time, ...
4
votes
1answer
2k views

The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why?

My question is why the dynamic programming of the knapsack problem does run in polynomial time? The question is answered here Why is the O(nW) algorithm for the Knapsack problem not a polynomial one? ...
4
votes
1answer
255 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 ...
4
votes
2answers
139 views

Resource bounded reductions for RE-Complete problems

Given that the halting problem is RE-Complete, we can reduce any problem in RE to an instance of the halting problem. Are there are any results on the time-bounds for this reduction? Can we do this ...
4
votes
2answers
99 views

On certificates in BPP (avoiding majority vote)

Assume that we have a $BPP$ algorithm $A$ for a problem $\Pi$. Given input $x$ we run $A$ on $\Pi$ polynomially many times and take majority output. However if the problem $\Pi$ is also in $NP$ ...
4
votes
1answer
225 views

Can we use reductions to design approximation algorithms for NP-hard problems?

Let us say that I have a problem $P(n)$ that I need to solve (where $n$ is the size of the input of problem $P$). I used a polynomial-time reduction from a known NP-hard problem $Q(m)$ (where $m$ is ...
4
votes
1answer
50 views

Probability of randomly designated subsets cover the universe

Let $U=\{1,2,\ldots,n\}$ and $S \subseteq \mathscr{P}(U)$. Let $T$ be a subset of $S$, randomly constructed selecting independently each element of $S$ with probability $p$. Is there a polynomial ...
4
votes
1answer
76 views

Machine with an oracle for a language that cannot decide another language in polynomial time

We usually see examples of languages contained in $P^A$ for some language $A$, or cases where $P^A=P^B$ (or $P^A\subseteq P^B$) for two languages $P^A$ and $P^B$. However, there is any explicit ...
4
votes
1answer
56 views

Maximize function over a set with a transitive and antisymmetric relation

Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$. For any set $S\subseteq X$ define $\Gamma(S)=\left\{y\in S \mid \not \exists x\in S . (x,y)\in\mathcal{R}\...
4
votes
1answer
176 views

Is there a known way to convert any $QBF_2$-formula into an equisatisfiable $QBF_2$-formula in CNF in polynomial time?

It is easy to turn any boolean formula and any quantified boolean formula into an equisatisfiable formula in CNF using Tseitin transformation: $$ Q_1 z_1 Q_2 z_2 \ldots Q_n z_n \Phi \Rightarrow Q_1 ...
4
votes
1answer
313 views

Simulate NPDAs with DTMs using only polynomial overhead

We know by polynomial-time parsing algorithms like the classical CYK algorithm that $\mathrm{CFL} \subseteq \mathrm{P}$. Furthermore, it is easy to show by direct simulation that $\mathrm{DCFL} \...
4
votes
1answer
589 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 $k$? ...
4
votes
1answer
40 views

On the hardness of constraint satisfaction

I am interested in the hardness of the following question. Suppose we have a vector of $n$ optimization variables $\mathbf{x} = \langle x_1, . . ., x_n\rangle $ and $m$ vectors $\mathbf{v}_1, . . .,\...
4
votes
1answer
69 views

Conditional lower bounds on the running time of the single source shortest path problem

Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
4
votes
0answers
238 views

Subset Sum Search Problem for Input with At Most One Solution [closed]

Edit: This question has been reasked on TCS. We first consider the search version of the subset sum problem: Given a set $S$ of $n$ naturals, find a subset of $S$ that sums to exactly $W$. My ...
4
votes
0answers
341 views

Time complexity of languages recognized by linear bounded automata with restricted number of writes

Suppose that $L$ is a language recognized by a linear-bounded automaton with the constraint that it can only change each of its input cells at most $t$ times each, where $t$ is some constant integer. ...
4
votes
0answers
99 views

Polynomial time algorithms on strings [closed]

I am looking for familiar problems on strings of finite length over an finite alphabet, where a polynomial time algorithm is known. To be more precise, let $\Sigma$ be a finite alphabet. I am looking ...
3
votes
2answers
903 views

Solve parity game in polynomial time?

Is it possible to solve a parity game in polynomial time? If yes, how? If no, why not?
3
votes
1answer
185 views

Why is the set of perfect squares in P?

I am reading an article by Cook [1]. In it he writes: The set of perfect squares is in P, since Newton's method can be used to efficiently approximate square roots. I can see how to use Newton's ...
3
votes
2answers
122 views

For some $n$, how can we check whether there exists $a,b \in \mathbb{N}$ such that $a^b = n$ in polynomial time?

For some given $n$, how can we check whether there exists $a,b \in \mathbb{N}$ ($b > 0$) such that $a^b = n$ in polynomial time with respect to the number of digits in $n$?
3
votes
3answers
3k 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 ...
3
votes
2answers
1k 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 ...
3
votes
2answers
2k 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$
3
votes
1answer
90 views

Is rejecting in polynomial time required for language to be in P?

Language $L$ is in $\mathrm{P}$ if and only if there exists some Turing Machine $M$ such that for every word in $L$, $M$ either accepts or rejects it in polynomial time. Right? But what if all we ...
3
votes
1answer
129 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 ...
3
votes
1answer
413 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
2answers
1k 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 ...
3
votes
2answers
1k views

Is it true that P is not equal to deterministic linear space complexity class?

I'm curious, how could I know that P (polynomial time complexity class) is not equal to deterministic linear space complexity class? Is there some proof? Or should I find some algorithm which is not ...
3
votes
1answer
567 views

How do we show that the polynomial time reduction of one problem to another has been done in polynomial time?

I have just been reading through a SO post which proves that the Halting Problem is NP-Hard. Whilst this is an easily followed proof, one slight slight aspect of it has left me scratching my head: it ...
3
votes
1answer
69 views

Do poly-time algorithms exist whose time complexity is unprovable?

If not, is there a decision procedure that successfully classifies any polynomial time algorithm as poly-time within a time polynomially bounded by the length of the input algorithm?
3
votes
1answer
2k views

Are there any coP problems

Is there a notion of coP problem? Also is there a notion of every problem being reducible to one problem in P (like 3SAT in NP completeness)?
3
votes
2answers
483 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 ...
3
votes
1answer
381 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 ...
3
votes
1answer
17 views

Is it OK to change any polynomial time to another polynomial time without breaking equivalency of Turing machines?

Is it true that adding to a Turing-machine-equivalent an "oracle" calculating any polynomially calculable (in this machine) function using some other nonzero polynomial time than this ...
3
votes
1answer
70 views

Partitioning a bipartite graph to get disjoint components of same size

I have a bipartite graph $G = (V, E)$ where $V = S \cup T$ is the division into the two halves. I want to select $n$ elements from $S$ and $nk$ elements from $T$ such that the graph they generate has $...
3
votes
1answer
308 views

Equality of cardinality of maximum matching and minimum vertex cover in general

I'm preparing for exam and I came across this problem: We say that a graph is König's graph when the sizes of its minimum vertex cover and maximum matching are equal. Find a polynomial time ...
3
votes
1answer
195 views

How does this proof show that sequences of $O(1)$ polynomially bounded Kolmogorov complexity are NOT the polynomial computable ones?

I'm trying to understand a proof from the paper: Balcázar, José L.; Gavaldà, Ricard; Hermo, Montserrat: Compressiblity of infinite binary sequences, Published in: Complexity, Logic, and Recursion ...
3
votes
1answer
532 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
2
3 4 5
7