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
0
votes
1answer
30 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 ...
0
votes
0answers
34 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 ...
1
vote
1answer
24 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 ...
0
votes
0answers
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 ...
1
vote
0answers
67 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 ...
0
votes
1answer
57 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? ...
1
vote
0answers
26 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 ...
-1
votes
1answer
38 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 ...
0
votes
1answer
74 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,...
-1
votes
2answers
52 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
0
votes
0answers
30 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 ...
1
vote
1answer
62 views

Polynomial-Time reduction from Partition to MakeSpan

Partition Problem: Input: $A:=$ {$a_{1}, ..., a_{n} $}. $a_{i} \in \mathbb{N}$ $\forall i \in$ $\{1, \ldots, n\}$. Question: Exists a subset $A_{1} \subset A$ with: $\sum_{a_{i} \in A_{1}} a_{i} = \...
0
votes
0answers
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 ...
2
votes
0answers
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?
0
votes
1answer
56 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. ...
0
votes
1answer
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 ...
1
vote
1answer
72 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?
1
vote
1answer
46 views

building a polynomial algorithm that solves SAT when given a polynomial TM that solves SAT on two formulas

Here's the question: Assume there exists a polynomial time machine $M$ that receives two formulas $\varphi_1,\varphi_2$ and satisfies the following: If $\varphi_1 \in \mathrm{SAT}$ and $\...
0
votes
0answers
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 ...
0
votes
0answers
17 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 ...
1
vote
1answer
36 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 ...
0
votes
0answers
12 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 ...
1
vote
1answer
32 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 ...
2
votes
1answer
28 views

Polynomially related encodings

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_{...
0
votes
0answers
37 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 ...
1
vote
1answer
163 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/...
0
votes
1answer
40 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 ...
2
votes
1answer
244 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 ...
1
vote
1answer
17 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 ...
7
votes
1answer
869 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 ...
0
votes
0answers
32 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 ...
2
votes
1answer
32 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 ...
0
votes
1answer
27 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 ...
1
vote
1answer
19 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} \...
0
votes
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-...
5
votes
0answers
127 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{...
4
votes
1answer
37 views

On the hardness of constraint satisfaction

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, . . .,\...
1
vote
0answers
26 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 ...
1
vote
1answer
56 views

What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?

If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(...
0
votes
0answers
18 views

Proof that Special case of SUBSET SUM is in P [duplicate]

So i know that SUBSET SUM is in NP. But given the following special case: The numbers $\ a_i,...,a_n $ with $\ i= 1,...,n-1 $ fulfill the condition: $\ a_i|a_{i+1} $ ($\ a_i $ divides $\ a_{i+1} $) ...
3
votes
1answer
62 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 ...
2
votes
1answer
137 views

How undecidable is it whether a given Turing machine runs in polynomial time?

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 ...
5
votes
2answers
136 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 ...
4
votes
1answer
68 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 ...
2
votes
1answer
46 views

Are chaotic systems computable in polynomial time

Suppose the parameters/inputs of the computation include the time at which the configuration of a particular deterministic chaotic system needs to be computed. Say, for instance, as input we have a ...
1
vote
0answers
149 views

Min-Ones-2-SAT getting to vertex cover

In the Min-Ones-2-SAT problem, we are given a 2-CNF formula φ and an integer k, and the objective is to decide whether there exists a satisfying assignment for φ with at most k variables set to true....
1
vote
2answers
318 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 ...
1
vote
1answer
24 views

Use Fact to decompose a given number

Let Fact be the following decision problem. Given two natural numbers $k \le n$ the machine accepts if and only if $n$ has a non-trivial divisor that is less than or equal to $k$. Prove that if Fact $\...
0
votes
1answer
190 views

Difference Between PTAS and FPTAS [duplicate]

According to this link: Polynomial Time Approximation Scheme (PTAS) is a type of approximate algorithms that provide user to control over accuracy which is a desirable feature. These algorithms ...
2
votes
0answers
23 views

Useful conditions for proving super polynomial lower bound for some kind of recurrences

Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$ Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have ...

1
2 3 4 5
7