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

379 questions
Filter by
Sorted by
Tagged with
16 views

### Does a constant time compression algorithm proves that P=NP?

Supposed someone came up with a compression algorithm that doesn't iterate through bytes or anything to compress data, does that proves P=NP? That is, an algorithm that doesn't rely on patterns/...
762 views

### Determining if an NFA accepts an infinite language in polynomial time

Can we determine in polynomial time if the language accepted by an NFA is infinite? The case of DFA is simple, but converting an NFA to a DFA may take exponential time. Also, I ran into this post, ...
12 views

1 vote
33 views

### Is the clique problem polynomial-time solvable still in unit disk graphs allowing different sized disks?

Clark et al. proved that the clique problem is polynomial-time solvable in unit disk graphs. Does anyone know if this result holds still if the disks are allowed to be different sizes? Or do such &...
38 views

### Using the chromatic number to compute an optimal coloring

Suppose we are given a graph $G$ of order $n$ and a black box that can efficiently (polynomial time) compute the chromatic number $\chi(G)$. I am curious to hear how would one go about in order to ...
660 views

### Proofs of reduction of any hard problem

Approach:1 To prove any unknown problem $B$ is NPH then take any known NPH problem $A$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $A$, then ...
198 views

### If $A\leq_m^\mathsf{}B$ and $B$ is a regular language, does that imply that $A$ is a regular language?

Corollary:1 We know that if $A\leq_m^\mathsf{}B$ and $B$ is decidable then $A$ is also decidable. This is because if there exists a specific algorithm for solving $B$ and we can also reduce $A$ to $B$ ...
77 views

### Reduction from recursive language to recursive enumerable

If any language $L_1$ reduces $L_2$ in polynomial time $L_1\leq_p^\mathsf{}L_2.$ If $L_1$ is recursive then $L_2$ is recursive and recursively enumerable, is it true? Because $L_2$ is at least as ...
36 views

### Do graphs with a bounded number of incident edges have a polynomial-time subgraph-isomorphism algorithm?

It is well known that the subgraph isomorphism problem is NP-complete. And so a polynomial-time algorithm for solving it would mean P = NP. Thus I'm interested in whether a bounded version of the ...
57 views

95 views

### What is wrong with this argument that if A is NP Complete, but B is in P, then A\B is NP Complete and B\A is NP Complete as well?

The following seems to me to be relevant to this question, but to me is an interesting exercise, especially since I have not formally worked with complexity before, but I want to learn more: Suppose ...
Studying for my finals in Complexity theory. This question comes up in different variants and it requires to use probability. A side note before, to be more clear: A CNF clause consists of $n$ clauses ...
I need some help with this question: Definition: A Turing-machine that is a counter for the language $L$ is called 'polynomial counter' if there exists a polynomial $p$ s.t. every word $w\in L$ ...