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

349 questions
Filter by
Sorted by
Tagged with
55 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 ...
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 ...
33 views

18k views

### Why is linear programming in P but integer programming NP-hard?

Linear programming (LP) is in P and integer programming (IP) is NP-hard. But since computers can only manipulate numbers with finite precision, in practice a computer is using integers for linear ...
58 views

### Reconstructing an Array via Time-Intensive Subset Queries

I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem. I am given access to an ...
33 views

### Relations between deciding languages and computing functions in advice machines

I'm trying to understand implications of translating between functions and languages for P/Poly complexity. I'm not sure whether the following all makes sense. Giving it my best shot given my current ...
14 views

### Global-input-local-output p-time algorithms

Are there polynomial-time algorithms whose input is global but output is local in nature? What I have in mind is a problem instead of an algorithm. It’s the satisfiability (SAT) problem. Each clause ...
59 views

### How to prove P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?

How to prove if P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP? OR P = NP if NPC intersects with Co-NPC
77 views

### Can we decide if a number is a power of any given $K$ in polynomial-time?

It is simple to decide powers of 2 in $O(n)$ time because it's just "0-bit Unary" after bit-1. (eg. $1000$ is a power of 2 in binary). I haven't found many other trivial powers of $K$ that ...
58 views

### Given arbitrary integers of $K$ and $M$, can deciding $2^K$ + $M$ is a prime be in $P$?

Given arbitrary integers of $K$ and $M$, is $2^K$ + $M$ a prime? ...
27 views

### Seeking guidance on what to read for Feasibility Binary IP with ''almost total unimodular'' (-1, 0, 1)-Coefficient Matrix and No Obj Function

I am working on an algorithm in graph theory which I wish to prove it's polynomiality/NP-hardness. I am investigating a binary variable (0, 1) integer program which has the coefficient matrix ...
68 views

### Do all languages in $P$ have polynomial proofs that they are in $P$?

A proof for a language $L$ belonging to a complexity class $C$ can be framed as there existing a verifier $V$ that accepts this proof as the first part of their input and the language as the second. ...
123 views

### "Given an algorithm, decide whether it runs in polynomial time" is this problem in NP?

This problem is not decidable (reducible to halting problem) but is semi-decidable and therefor verifiable (as those two definitions are equivalent: How to prove semi-decidable = verifiable?). However,...
78 views

### Decide if a string is a member of a language that represents $P$?

For some enumeration of the complexity class P (such as this as an example: How does an enumerator for machines for languages work?), for each string 𝑝 in the enumeration, does there exist some other ...
34 views

### Looking for fast LP solver algorithm for my Special case

I am interested to know what is the fastest algorithm (complexity wise) known to us to solve the following linear program. Due to its simplicity, I hope for a very fast algorithm. Your help is greatly ...
194 views

37 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 ...
55 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 ...
352 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/...
49 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 ...
321 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 ...
33 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 ...
920 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 ...
83 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 ...
64 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 ...
30 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 ...
287 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 ...
25 views

142 views

27 views

### Looking for some references on voting theory

After reading through this paper on optimizing the sum of sigmoid functions, http://www.web.stanford.edu/~boyd/papers/pdf/max_sum_sigmoids.pdf, I am interested in the problem addressed in section 7.3 ...
70 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 ...
1k views

### What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time?

Here we see a very interesting attempt to show that $\mathrm{P} \ne \mathrm{NP}$ by Norbert Blum. Here we see 116 previous attempts at solving P vs. NP. Here we see the P vs NP problem defined as: ...
83 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 ...
The proof of Theorem 1 that PTime is not semi-decidable in this recent preprint effectively shows that it is $\mathsf{R}\cup\mathsf{coR}$-hard. The proof itself is similar to undecidability proofs at ...