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
24 views

Reduction of np to npc

Given that $A$ is $NPC$ problem. And I need to check "if $D$ belongs to $NP$ and $D\leq_p^\mathsf{}A$ then $D$ is $NPC$" is true or not? My approach: Since $D\leq_p^\mathsf{}A$, therefore $...
1
vote
1answer
24 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 &...
2
votes
1answer
24 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 ...
4
votes
1answer
618 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 ...
0
votes
1answer
83 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$ ...
0
votes
1answer
52 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 ...
2
votes
1answer
25 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 ...
0
votes
1answer
29 views

If $A\leq_P B$ and $B\in \text{NP}$, is $A\in \text{NP}$?

Let $A\leq_P B$ mean that the language $A$ is polynomial time reducible to $B$. It is a theorem that $A\leq_P B$ and $B\in \text{P}$ then $A\in \text{P}$. My question is, if $A\leq_P B$ and $B\in \...
2
votes
3answers
566 views

Are there problems in NP that do not reduce in polynomial time to any problem in NP?

As the title says: are there problems in $\mathbf{NP}$ that do not reduce in polynomial time to any problem in $\mathbf{NP}$?
3
votes
2answers
87 views

Subset Sum With Interval Target

Define the subset sum with interval target problem (SSITP) as follows: SSITP Input: A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$ such that $\sum_{a_i \in S} a_i = T$. SSITP Output: ...
1
vote
0answers
44 views

Does an FPTAS exist for the multiple subset sum problem when m is fixed and c is not a variable?

From Wikipedia Multiple subset sum: The multiple subset sum problem (MSSP) is a generalization of the subset sum problem (SSP): given a multiset $S$ of $n$ integers, and an integer $m$, the goal is to ...
0
votes
0answers
37 views

Pseudo-polynomial Algorithms

Reading wikipedia I found that they give this example Consider the problem of testing whether a number n is prime, by naively checking whether no number in $\{2,3,\dotsc ,\sqrt {n}\}$ divides $n$ ...
0
votes
1answer
30 views

Differences between Polynomial and fully polynomial time approximation scheme

I have a confusion on understanding the relation between: The input n ,The relative error and The running time of the program In both PTAS and FPTAS. In "The running time of PTAS must be ...
0
votes
1answer
28 views

Polynomial and fully polynomial time approximation scheme

How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program? Is there any other way to decide?
2
votes
1answer
52 views

Is there a difference between extremely slow growing functions and constants with respect to computable functions?

So let's say we have the function $f(n)$ that gives $k$ such that $k$ is the smallest number that gives a busy beaver function $B$ value from input $k$ that is greater than $n$. Or more succinctly the ...
1
vote
2answers
123 views

Need the type of time complexity and its formula

If the complexity of my problem is $O(f_n(n))$ begins at $n =4$ and increases in this sequence: At $n = 4$ the number of operations = $(n - 2)$, $n = 5$ the number of operations = $((n - 2) (n-2)(n-...
-4
votes
3answers
79 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 ...
2
votes
2answers
94 views

Satisfiable CNFs where each clause contains logarithmically many different literals

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 ...
1
vote
2answers
76 views

"Polynomial Counter" Turing Machine

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$ ...
0
votes
1answer
39 views

Is this variation of Max-Coverage NP-hard?

Setup An instance of Max-Coverage is typically defined by a collection of $n$ sets $S = \{s_1, s_2, \dots, s_n\}$, and a budget $k$, where the objective is to select a subset $U\subset S$ such that $$\...
1
vote
1answer
21 views

NP problem: certificate concept clarification

When proving a problem in NP, e.g. k-clique problem defined as k-clique:= {<G,k>| G has a clique of size at least k }, from what I understand is that all we assume for the certificate "c&...
1
vote
0answers
45 views

What computational hardness concept corresponds to strongly-polynomial time algorithms?

Consider the computational problems in which the input is a set of $n$ integers with maximum magnitude $M$. According to Erik Demaine's lecture notes, assuming $P\neq NP$, the following are true: If ...
0
votes
0answers
49 views

A paper claiming that optimization version of symmetric TSP can be solved in polynomial time

In the following paper : Czopik, J. (2019) An Application of the Hungarian Algorithm to Solve Traveling Salesman Problem. American Journal of Computational Mathematics,9, 61-67. In the Introduction, ...
2
votes
1answer
90 views

Is there an FPTAS for 3-way number partitioning?

The maximization problem of the 3-way number partitioning reads as follows: given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...
0
votes
1answer
77 views

IS SUBSET-SUM in P if b(the sum) is given in unary and a1,...,an is in binary?

The SUBSET SUM decision problem consists of poitive integers a1,...,an; b. We wish to know if for some subset S of the indices, $\sum_{i \in S}a_i = b$ I want to prove that if b is given in unary(...
2
votes
1answer
48 views

How is Hypergraph Isomorphism (HI) reduced to Graph Isomorphism (GI) in polynomial time?

This question states that the problem of Hyper-graph Isomorphism is equivalent to Graph isomorphism. I have not been able to find a description of the reduction so I am wondering how that might work ...
1
vote
1answer
24 views

Can PTAS $\epsilon$ parameter be dependent on the algorithm input?

Let A be a PTAS algorithm with time complexity $O\left(\frac{1}{\epsilon}\right)$. Let $n$ be the input of the algorithm A. From Wikipedia: The running time of a PTAS is required to be polynomial in $...
3
votes
1answer
17 views

Is it OK to change any polynomial time to another polynomial time without breaking equivalency of Turing machines?

Is it true that adding to a Turing-machine-equivalent an "oracle" calculating any polynomially calculable (in this machine) function using some other nonzero polynomial time than this ...
1
vote
1answer
33 views

Constant-time adding an element?

Is a computer with infinite memory and infinite word size a Truing machine equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) if we ...
3
votes
1answer
33 views

Complexity of pattern matching for modus ponens logical conclusions

Is a Turing machine with added the following contant-time operation equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) to a (usual) ...
1
vote
1answer
76 views

How to prove NP-completeness of this mail-problem?

Let's say we have n postmen that are bringing people mail in a neighbourhood, and that they start and end at the same post office. This situation can be decribed with a directed graph, where the ...
1
vote
1answer
43 views

Maximum Subarray Problem - Analyzing best case, worst case, and average case time complexity big o

New to the board, if this is the wrong section I apologize and I will delete it. Will be helpful to be provided correct exchange to guide me through this process of learning. If you have a given an ...
1
vote
0answers
45 views

Optimize binary multivariate polynomial multiplication

You have a few variables that can only assume the values 0 or 1 and you use those to form two polynomials. Is there a way to multiply the two polynomials that is faster than O(n²) where n is the ...
1
vote
1answer
72 views

Is it possible fo find a vertex-cover of size $\lceil \log |V| \rceil$ in polynomial time?

If we have a graph $G=(V,E)$, can we find a vertex cover with size $\lceil \log |V| \rceil$ in polynomial time?
0
votes
1answer
41 views

is advice function and an oracle the same thing?

In the context of P/poly complexity class, an advice function is mentioned. How is the advice function different than an oracle(/certificate)? https://en.wikipedia.org/wiki/Advice_(complexity) https://...
0
votes
0answers
59 views

IF satisfiability problem belonged to P, can the certificate be found efficiently?

IF SAT(satisfiability problem) belongs to P, then is it possible for a certificate of an arbitrary instance of SAT to be found efficiently?
1
vote
1answer
193 views

Is this clique algorithm in polynomial time correct or might it have another time complexity?

I came up with the idea finding a k-clique through starting at a small s-clique (like 1-,2- or 3-clique) and use it to find every s+1 Clique iterative. I had some trouble finding the Time Complexity ...
0
votes
3answers
94 views

Does exponential time always beat polynomial time? $n^{\frac{1}{2}}$ vs $2^{\sqrt{log \,n}}$

I was told that exponential time always beats polynomial time but doesn't this not work for: $n^{\frac{1}{2}}$ vs $2^{\sqrt{log \,n}}$? If we take $log_2$ on both of them we get: $\frac{1}{2}log \,n &...
0
votes
1answer
63 views

Minimum absolute value of subset sums of integer values

$f(x_1,...,x_m)=\min_{\emptyset\subset I\subseteq[m] }\left|\sum_{i\in I}x_i\right|, x_i\in \mathbb{Z}\setminus\{0\}$ How to prove $f\in \mathbf{POLY} \Leftrightarrow \mathbf{P}=\mathbf{NP}$? When $\...
1
vote
1answer
51 views

Why every finite language is polynomial?

I understand that it's possible to build TM that check all the finite number of cases, so it's definitely in $R$, but I'm not sure why it's in $P$
1
vote
1answer
141 views

Given a CFG G (in Chomsky normal form) and a string w, determine whether w has more than one parse tree in G in polynomial time

So I have the following language: C = {<G,w>|G is a CFG in Chomsky normal form and w has more than one parse tree in G} How to prove that this language is in P (decidable in deterministic ...
1
vote
1answer
54 views

How to check if an algorithm's running time is linear/polynomial in its input size? Multiple variables

I am reading a proof that the Subset Sum decision problem is NP-complete. I know that the time complexity is always calculated based on the number of bits of the input in binary, hence the $\log{W}$. ...
2
votes
1answer
55 views

Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time

I am looking for an algorithm for approximating the chromatic number of an undirected simple graph with $n$ vertices in $O(n^{c_1})$ time and $O(n^{c_2})$ space, for some constants $c_1$ and $c_2$. ...
1
vote
0answers
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 ...
-1
votes
1answer
33 views

Permutation Array

Hello I have a problem and would like a help to prove if it is P or not. Given an array $\mathcal{A}$ of integers. Is there a permutation of the elements of $\mathcal{A}$ such that, $\forall i \in \{...
0
votes
0answers
26 views

A set that is not polynomial time enumerable

For a set $I\subseteq \Bbb N$, defined $s_{I}(n)=\min\{i\in I\mid i>n\}$. The set $I$ is called polynomial-time-enumerable if $s_I(n)$ is computable in $\mathsf{poly}(n)$ time. Most of the sets I ...
0
votes
0answers
112 views

Why does converting a NDTM to a a DTM result in a higher time complexity?

I feel like I am really close to understanding the difference between P vs NP, and I think it comes down to this. The confusion stems from the fact that both P and NP problems are done in polynomial ...
2
votes
0answers
245 views

Strong polynomial time algorithm for deciding LP feasibility

Let $$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
4
votes
3answers
79 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 ...
0
votes
1answer
57 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 ...

1
2 3 4 5
7