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
2answers
377 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
811 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
1answer
2k 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 ...
4
votes
3answers
4k 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
1answer
3k 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 ...
4
votes
2answers
2k 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
2answers
858 views

Why is it important to solve a problem in Polynomial time, In cryptography?

I have just started to learn Cryptography. I am trying to learn "Merkle-Hellman Knapsack Cryptosystem". So, right at the beginning of the discussion, a question came in my mind: Why is it important ...
4
votes
1answer
197 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
1answer
128 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
235 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
117 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
98 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
147 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
45 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
544 views

Linear programming restricted to rational coefficients

I'm reading the appendix A of Williamson's "the design of approximation algorithms" about linear programming. In the definition of a linear programming it restricted the coefficients of cost function ...
4
votes
1answer
72 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
291 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
539 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
37 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
68 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
196 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
144 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
93 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
854 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
2answers
117 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
2k 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
1k 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
87 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
128 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
338 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
1answer
545 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 ...
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
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? ...
3
votes
1answer
344 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
2answers
444 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 ...
3
votes
2answers
206 views

GOTO vs. including line in loop - will it affect efficiency?

Let's say I have an algorithm something like as follows: ...
3
votes
1answer
67 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
424 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
347 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
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
293 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
498 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 ...
3
votes
2answers
831 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
62 views

Functional problem and verifying solutions

Is there a functional problem for which there is an algorithm that can decide if a solution is a solution or not in polynomial time but we can't find a solution in polynomial time? Let FP be the ...
3
votes
1answer
45 views

Number of equivalence classes in $P$

I am currently taking a course which involves computational complexity. I was told that polynomial equivalence (polynomial time reduction) divides P into exactly 3 equivalent classes, namely $\phi$ , $...

1
2
3 4 5
7