Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# 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.

266 questions
Filter by
Sorted by
Tagged with
43 views

### Theoretical performance measures other than worst case

Suppose that $P \neq NP$, and $P = BPP$. Assume one is given a decision language $L \in NPC$, and she has only polynomial time turing machines. Additionally, she can't use randomness (not sure that's ...
82 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 ...
194 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. ...
47 views

### Longest cycle, existance of approximate algorithm implies existence of better one

This is an exercise from an old exam that I don't know how to solve. For any undirected graph $G$, let $c(G)$ be the length of the longest (simple) cycle in $G$. Show that if there exists a ...
48 views

### Shorten Length Reduction

I've stumbled upon this Question: We say that a reduction $f$ of a language $A$ to a language $B$ is a Shorten length reduction, if there exists a number $n\in N$ s.t for every $w\in A$, s.t ...
47 views

### Cobham's characterization of FP

Does anyone know of an accessible introduction to Cobham's model independent characterization of FP and it's equivalence to the standard definition using Turing machines? The best source I could find ...
74 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 ...
765 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.
166 views

110 views

### Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology?

Is the following true or false? Why? Let $Y$ denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of $Y \leq_{p} X$.
72 views

### Polynomial Complexity (Relative to the Size of the Input)

I came across the following statement: "Since b is smaller than n, the complexity $O((n + mb)^3)$ is polynomial." I suppose it has something to do with the notion of polynomiality in terms of the ...
265 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 ...
33 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 ...
87 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?
586 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$. ...
282 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? ...
60 views

56 views

### P/NP - Polynomial Reduction vs Certificate

I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate. How I understand polynomial reduction is that you can use it to ...
23 views

31 views

### Determine whether a system of $n$ linear equations has solutions in $\{0, 1\}^n$ in polynomial time

I'm trying to determine whether it is possible to decide if a system of $n$ linear equations with integer coefficients and $n$ variables has a solution in $\{0, 1\}^n$ in polynomial time. ...
90 views

### Find Hamiltonian cycle in polynomial time

I want to know for what types of graph it is possible to find Hamiltonian cycle in polynomial time. It would be helpful also to show why on some types of graph finding Hamiltonian cycle would be only ...
201 views

### Relation beetween log-space reduction and polynomial time reduction

I read somewhere that given two languages A and B, if A <=(log) B, then A <=(P) B (with <=(log) the log-space reduction and <=(P) the polynomial time reduction), but I'm not sure about the ...
159 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(|...
28 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: ...
225 views

84 views

### 2-clause satisfiability associated graph

A 2-clause is a clause with at most two propositions (clauses?) : $(p \wedge q,\neg p \wedge q, \neg p,...)$. I have to show that the folllowing problem is $\in$ P: 2-SAT: Input : A conjunction $\Phi$...
50 views

### How to reduce constrained proofs to 0-1 IP

Consider the following problem: Can $X$ be proven in fewer than $Y$ steps, from axioms $Z$, with finitely many transition rules $\tau$? This lies in $NP$, since if I supply a proof $M$, and ...
58 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 ...
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 Turing-...