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

308 questions
Filter by
Sorted by
Tagged with
269 views

### CRC computation speed vs polynomials features

I tried to find information about how features of a CRC polynomials influence computation speed of implementations. It is obvious that (depending from the CPU architecture the algorithm runs on) ...
24 views

### Are there P problems with no known polynomial-time algorithm? [duplicate]

As the title says, I'm just curious if there are any problems with polynomial-time algorithms, but where no polynomial-time algorithm for it is currently known? Of course, this question would be ...
28 views

76 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 ...
42 views

### Why we can't have some algorithm to be polynomial if there are generic conditions that make them so?

I explain it better: There are some algorithms that is clearly in NP, also NP-complete, but that under certain conditions they can be solved in polynomial time. An example is Bin Packing, the decision ...
60 views

26 views

### What's the class of problems solvable in polynomial time with an exponential number of processors?

What's the class of problems solvable in polynomial time with an exponential number of processors? I am asking this because I'm curious about the class of problems that could feasable be solved on a ...
31 views

### Are there problems that are known to be in ZPP but not in p

Are there any problems that are known to be in ZPP but not in p?
26 views

### Is there a polynomial time algorithm for this decision problem?

Is there a factor in $M$ that is $>$ $1$, but $<$ $M$ that is NOT a factor of $N$? False Result Example $N$ = 8 $M$ = 16 1, 2, 4, 8, 16 There is no integer that is NOT a factor of $N$ that ...
76 views

### Is co-P recursively enumerable?

P is RE, but is the complement of the class of languages decidable in polynomial time also recursively enumerable? If both are RE then this makes P recursive?
11 views

### Logic of the squared running time in “A Variant of Nondeterministic Acceptance”

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman, Motwani where I came across the following claim: A Variant of ...
19 views

### Applying Polynomial Time Approximation Scheme (PTAS) on an Algorithm

I am trying to apply PTAS on an algorithm. I think that we apply PTAS on the running time equation of the algorithm. We use the term (1-ϵ) and (1+ ϵ) in the running time of the algorithm but I don’t ...
54 views

### Is longest-path with a specific source and destination impossible in polynomial time?

The problem of finding the longest path in a graph is known to be not be possible in polynomial time, that I am aware of. I am also aware that using DFS or BFS can give the shortest distance between a ...
19 views

### Search reduction to decision

I'm a little stumped on this question (and I don't know the name of it, which is why I've excluded it from the title). I need to describe an algorithm that finds a solution to an NP-Hard problem given ...
CLRS states that: For some set $I$ of problem instances, we say that two encodings $e_1$ and $e_2$ are polynomially related if there exist two polynomial-time computable functions $f_{12}$ and $f_{... 1answer 33 views ### Is there an efficient algorithm for determining the probability a large randomly chosen integer is not divisible by any integer of some set? Given a set of 10 integers$A = a_1, a_2, \cdots a_{10}$, is there an efficient algorithm which can tell me what's the probability a randomly chosen integer between$1$and$10^{10}$is NOT divisible ... 0answers 42 views ### Why is “encoding” important in time complexity? I read many writing about the time complexity of 0-1 knapsack problem. (https://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial#answer-4538668) In conclusion, the ... 1answer 233 views ### 0-1 knapsack without repetition My question is why O(nW) at the knapsack problem is pseudo-polynomial. I read lots of the explanation at stackoverflow, But I don't really understand it. (https://stackoverflow.com/questions/19647658/... 1answer 44 views ### What types of string properties are verifiable in polynomial time? When given the string and the property in question as a potential certificate. Is there any classification theorem that says something along the lines of: all properties (of strings) that have this ... 1answer 498 views ### Show that the SAT Problem for CNF formulas with at most two occurences of each variable can be solved in polynomial time Assuming, I have an arbitrary CNF Formula in which each variable has at most two occurences, how can I proof/show that this can be solved in polynomial time? My first thoughts so far: because each ... 1answer 265 views ### Understanding definition of NP and co-NP From some of the texts I read, one definition of NP is: "An equivalent definition of NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine." and that we ... 1answer 24 views ### What does Bellantoni-Cook say about Cook-Reckov? In implicit complexity theory they construct natural programming languages that are complete for various complexity classes. An example, while there are many others, is Bellantoni-Cook where they ... 1answer 888 views ### Algorithms that run in polynomial time if P=NP On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking ... 0answers 51 views ### Solving NP problems : analogy between the SAT problem and the shortest path problem in this 2minute-long video https://www.youtube.com/watch?v=TJ49N6WvT8M (pulled from a free udacity course on algorithms/theoretical computer sciences), whose purpose is to show how a SAT problem can ... 1answer 53 views ### Is a DTM with k-tapes not the same thing as a NDTM with k-branches? In the definition of a complexity class like P, where they reference Deterministic Turing machines (DTMs), I don't see any restriction on # of tapes these DTMs are allowed to use. If a language L is ... 1answer 29 views ### An algorithm to determine probability of one string appearing earlier than another string in an evenly distributed binary sequence Given two binary strings of length$n$and$m$, determine in polynomial time the probability of the first appearance of one string being earlier than the first appearance of the other one in an evenly ... 2answers 186 views ### motivation and idea of defining non-deterministic Turing machine This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms ... 1answer 20 views ### Argument in proving that function is not polynomial time in bit length of input seems faulty I am currently solving a question that asks which of the following functions can be calculated in polynomial time: $$n!, \binom{n}{5}, \binom{2n}{n}, n^{\lfloor \lg n \rfloor}, \lfloor \sqrt{n} \... 1answer 1k views ### Is determining if there is a prime in an interval known to be in P or NP-complete? I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the ... 1answer 27 views ### Does the language defined in the details in NP-C or P? It's known that:$$ \textrm{CLIQUE} = \{(G,k): \mbox{G has a clique of size } k\} $$is \textrm{NP-C}, but what if every vertex has 2 neighbours (as defined in \textrm{2d-CLIQUE})?$$ \textrm{2d-... 0answers 135 views ### Is Geometric Disjoint Set Cover in P? I have come across the following optimisation subproblem: Geometric Disjoint Set Cover. Consider a collection$C$of (not necessarily distinct) ranges taken from a universe range$X \subset \mathbb{...
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, . . .,\...