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
1
vote
2answers
385 views

$DTIME(f(n)) \subset of DSPACE(f(n))$

I think this is again an easy one: $DTIME(f(n)) \subset DSPACE(f(n))$ They say its trivial but I dont see it, why? And would $DTIME(f(n^2)) \subset DSPACE(f(n^2))$ also be true? if yes why ...
1
vote
2answers
66 views

Time complexity for this simple loop

This is the code: j=2 while j<(n*n) j=j*j At first my approach was to treat this like this loop ...
1
vote
2answers
264 views

NP Class Definition of a Certificate

Given the definition for all x ∈ Σ∗ x ∈ L ⇔ ∃ u ∈ Σ∗ with |u| ≤ p(|x|) and M(x, u) = 1 Lets say the input x = ababab Then the certificate u shouldn't be longer than p(|x|). But what would be p(|...
0
votes
1answer
614 views

Polynomial-Time Reduction

I have read many resources, but I cannot understand what the polynomial-time reduction is. In everywhere, this is explained with standard-pattern sentences. Please can anyone explain it in detailed ...
2
votes
1answer
256 views

Time complexity of sum of $2^n$ values of polynomials

First a simpler question: let $q_{1}(k),\dots,q_{n}(k)$ be $n$ polynomials of degree smaller or equal to $n$. Let $f(n): \mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = \sum_{i=1}^{n}q_{i}(n)$. ...
3
votes
0answers
116 views

How to find a minimum spanning forest with a constrained number of nodes in each spanning tree?

Consider a weighted undirected acyclic graph consists of m source (root) vertices and n target vertices. The m-spanning tree problem of the graph is defined as that: (1) each of the m spanning trees ...
1
vote
2answers
34 views

If a decision problem $A \in \text{NP}$ and there exists reduction so that $A \leq_p B$, for decision problem B, what can be deduced about B?

I think that it implies that B can be solved by a non-deterministic polynomial time or worse Turing machine, but I realise that there is possibly some greater result that I'm missing. Thanks in ...
0
votes
1answer
1k views

Class P is closed under concatenation

Proving that Class P is closed under concatenation. The answer is given below: But I do not know why stage 2 is repeated at most O(n), could anyone explain this for me please?
7
votes
1answer
250 views

sequence of problems that take $\Theta(n^k)$ for increasing $k$?

Do we know an infinite sequence of decision problems where the most efficient algorithm for each problem takes $\Theta(n^k)$ time, where $k$ increases unboundedly? Suppose for example that we would ...
3
votes
1answer
45 views

Constructing an optimal solution to bin packing using a “magical function” $\phi$

I am taking an introductory course in complexity theory, and as an exercise, we were given the following problem. Consider the bin packing problem, with objects of positive (rational) weights $W = \{...
2
votes
1answer
67 views

Defining polynomial hierarchy with oracle machines and quantifiers

While trying to understand the concept of polynomial hierarchy, I noticed that there are several ways to define it. And the most confusing thing about the situation is to see the equivalence between ...
2
votes
1answer
49 views

Adding the requirement of linear time on infinitely many inputs into the class $P$

Is the following problem computable in polynomial time? Input: $<M_1>$, encoding of a determinstic TM that runs in polynomial time ($L(M_1)\in P$) Output: $<M_2>$, encoding of a ...
1
vote
1answer
29 views

How to prove that $n^d$ is $O(b^n)$ from $n$ is $O(2^n)$, given that $d>0, b>1$? [duplicate]

I'm reading Rosen's Discrete Mathematics and Its Application, at Page 212, it's about the "Big-O" notation using in computer science. This is the description in the book: And here is my reasoning: ...
3
votes
2answers
116 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
0answers
71 views

How to find m directed paths connecting the maximal number of vertices in an unweighted directed acyclic graph?

Consider an un-weighted directed acyclic graph (DAG) consists of m source (root) vertices and n target vertices. When there is only one source vertex (m=1), the problem to find a directed path ...
1
vote
1answer
391 views

Poly-time reduction is not antisymmetric

Lemma. (Transitivity) "$\leq_p$" is a transitive relation on languages, i.e., if $L_1 \leq_p L_2$ and $L_2 \leq_p L_3$, then $L_1 \leq_p L_3$. Proof. By definition, there are poly-time ...
1
vote
1answer
59 views

For which level of PH is $\operatorname{VALID}$ complete

I have the decision problem $\operatorname{VALID}$ which is the set of all valid propositional formulas (tautologies), I know that $$\overline{\operatorname{SAT}}\equiv_m^p \operatorname{VALID}.$$ ...
2
votes
1answer
243 views

Solving diophantine equations — does having a bound on the size of the solution help?

Let's define the following languages over the alphabet $\Sigma=\{0,1\}$: H10 is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ ...
3
votes
1answer
334 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 ...
4
votes
2answers
373 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 ...
0
votes
0answers
37 views

How about boolean formula that is satisfied on every reject path and falsified on every accept path of non deterministic Turing machine? [duplicate]

Cook-Levin reduction is both deterministic polynomial time and parsimonious and that's mean that from every non deterministic Turing machine $M$ and string $w$ it is possible in polynomial time ...
1
vote
1answer
498 views

What is the precise definition of pseudo-polynomial time (feat. Counting Sort)

From wikipedia In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required ...
1
vote
1answer
91 views

Polynomial time problems with provably high degree time complexity?

For any integer $k$, does there exist a decision problem in $\textbf P$ that can be proven to require $\Omega(n^k)$ steps?
0
votes
0answers
139 views

Linear time reduction equivalence

I have to show if the following statement is true or false. Suppose we have two problems $A$ and $B$. We want to know whether the following is true: If $A \le_p B$ and there is an algorithm which ...
4
votes
3answers
779 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 ...
0
votes
1answer
52 views

Solve Time Complexity problem using Time Hierarchy

I am trying to understand Time Hierarchy. I have an example that is solvable using the rules of Time Hierarchy. I would like an explanation on how to solve so that I may understand better how to use ...
0
votes
1answer
131 views

Whether the algorithm is polynomial or not with input size which is not polynomial [closed]

A problem may require memory space which is not polynomial with respect to the input size but may still have polynomial run time. Is this true or false? and why? any idea?
1
vote
1answer
51 views

If the difference between two oracles is negligible, is the difference between a PPT algorithm with these two oracles also negligible?

We say a negligible function is a function $\epsilon(n):\mathbb{N}\rightarrow \mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $n > N_c$, $$\...
2
votes
1answer
65 views

On lowness of $\oplus P$

$\oplus P$ is low for itself ($\oplus P^{\oplus P}=\oplus P$). Are there other complexity classes $\mathcal D$ that satisfy $\mathcal D^{\oplus P}=\oplus P$? Are there complexity classes $\mathcal C$ ...
0
votes
0answers
151 views

Prove that Vertex Cover belongs to NP

How to prove that the problem VERTEX-COVER belongs to $NP$? The problem VC is defined as follow: INSTANCE: Graph $G = (V,E)$ and an integer $k$ PREDICATE: Is there a subset $V_1 \in V $ s.t $\mid V_1 ...
1
vote
0answers
78 views

Must every NP-Complete Problem have a class of instances which is solvable in Poly time? [closed]

Is there any theorem that states that any NP-Complete Problem has a class of instances solvable in Poly time? For example, some problems like vertex cover are NP-Complete on general graphs but can be ...
3
votes
1answer
95 views

$m/p$-equivalence holds after union with an arbitrary finite language

Problem 1: Let $A,B$ be languages over some alphabet $\Sigma$, if $A \equiv_m B$, then for every finite language $C$, $A \cup C \equiv_m B \cup C$. Problem 2: Problem 1 but using polynomial time ...
4
votes
1answer
521 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 ...
1
vote
1answer
761 views

reducing $CLIQUE$ from decision to search problem

consider the language:$$CLIQUE = \left\{\langle G,k\rangle \ |\ \text{ $G$ is a graph containing a clique of size at least $k$ } \right\}$$ Suppose there's a polynomial time algorithm for $CLIQUE$. ...
38
votes
3answers
54k views

What exactly is polynomial time? [duplicate]

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 exponential....
2
votes
1answer
1k views

Question about NP problem certificates and P=NP

From my understanding a problem is considered to be in NP time if it can be solved in polynomial time with a non-deterministic Turing machine and verified in polynomial time with a certificate. My ...
2
votes
1answer
43 views

$UP^{\ O}\neq P^{\ O}$ for some oracle $O$

The definition of the class $UP$ is here. It is of course easy to see that $P\subseteq UP$. I have a problem of proving that there is an oracle $O$ and a language $L$ such that $L\in UP^{\ O}$ but $...
4
votes
2answers
193 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. ...
2
votes
0answers
89 views

polynomial time reducibility, if $A \in \mathbf P$ and $B \in \mathbf N$ $\mathbf P \setminus \{\emptyset,\Sigma^*\} $ and vice versa

$f: \Sigma^* \to \Sigma^*$ is a polynomial time computable function if some poly-time Turing Machine M, on every input w, halts with just $f(w)$ on its tape. Language $A$ is polynomial time reducible ...
2
votes
0answers
241 views

Building a poly-time verifier given a poly-time decider

Can I build a polynomial time verifier for problem, given a non-deterministic polynomial time decider for that problem? I assume I should modify the decider such that it will verify the certificate. ...
1
vote
1answer
359 views

Is the complement of MAX-CLIQUE in NP?

Let $$MAX-CLIQUE = \{\ <G,k>\ |\ G\ is\ an\ undirected\ graph,\ and\ the\ largest\ clique\ of\ G\ has\ k\ vertices\}$$ Does $MAX-CLIQUE\in coNP$? If it does, can you think of a verifier? If $NP=...
0
votes
1answer
76 views

If M is recognizing L in polynomial time, is it also deciding it in polynomial time?

Assume that a given turing machine $M$ accepts words in the language in $n^k$ or less steps, but words that aren't in the language are rejected in unknown number of steps (the machine might even ...
1
vote
1answer
76 views

For any non-trivial $A,B$, finding a language which both are polynomially reducible to

Given two non-trivial (not $\emptyset$ or $\Sigma^*$) languages $A$, $B$ over an alphabet $\Sigma$, which of the following is correct: a. There is a language $C$ such that $A\leq_pC$ and $B\leq_pC$. [....
1
vote
1answer
71 views

P decision problem that potentially requires at least $\Omega(n \log n)$ in the Turing model?

Currently, it is not proven that $NP \geq O(n \log n)$ in the Turing Machine Model. The weakness of this statement can be illustrated by NP-complete problems, which we think require way more time. ...
2
votes
1answer
86 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 ...
0
votes
1answer
299 views

GCD binary representation time complexity

1. Consider the following algorithm for deciding GCD: “On input : ...
3
votes
2answers
204 views

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

Let's say I have an algorithm something like as follows: ...
0
votes
2answers
272 views

approximation algorithm with polynomial complexity

It might be a silly question, I do take a carefully read about approximation algorithm through coursenotes, but when I saw the words "approximation algorithm with polynomial complexity", I can't ...
0
votes
0answers
27 views

Revisiting complexity of art gallery-like problem

In a question I had asked earlier, I was interested in knowing whether we could decide in polynomial time whether, for a directed graph $G$ with every one of its vertices belonging to an edge, a size-$...
6
votes
2answers
130 views

Time complexity of art gallery-like problem

Suppose that $G = (V,E)$ is a directed graph such that each vertex in $V$ is in at least one edge in $E$. We'd like to decide whether or not $w$ watchmen can be placed on $w$ distinct vertices in $G$ ...