People who code: we want your input. Take the Survey

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.

52 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
0answers
300 views

P vs NP and the Time Hierarchy

Assuming $P\neq NP$, is it possible that there exists a $k$ such that $P\subseteq\textsf{NTIME}(t^k)$? There reason I ask this is that I assume the following: $$P=NP \implies \forall k\ \exists j.\ \...
5
votes
0answers
142 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{...
5
votes
0answers
146 views

A matrix rank problem over finite fields

I have already asked a similar question here, but since I have not got an acceptable answer, I decided to ask a simpler version of the question here. Let $M|\mathbf w$, where $M$ is a matrix and $\...
4
votes
0answers
340 views

Time complexity of languages recognized by linear bounded automata with restricted number of writes

Suppose that $L$ is a language recognized by a linear-bounded automaton with the constraint that it can only change each of its input cells at most $t$ times each, where $t$ is some constant integer. ...
3
votes
0answers
48 views

Is a “stacked”, “local” version of 3-SAT NP-hard?

In this previous question, I learned that if each variable in a string $C \in 3\text{-SAT}$ appears only "locally", then finding a satisfying assignment is no longer NP-hard. My question below builds ...
3
votes
0answers
128 views

How to find a minimum spanning forest with a constrained number of nodes in each spanning tree?

Consider a weighted undirected acyclic graph consists of m source (root) vertices and n target vertices. The m-spanning tree problem of the graph is defined as that: (1) each of the m spanning trees ...
3
votes
0answers
74 views

How to find m directed paths connecting the maximal number of vertices in an unweighted directed acyclic graph?

Consider an un-weighted directed acyclic graph (DAG) consists of m source (root) vertices and n target vertices. When there is only one source vertex (m=1), the problem to find a directed path ...
2
votes
0answers
31 views

FPTAS for 3-way number partitioning

The maximization problem of the 3-way number partitioning reads as follows: maximize the smallest sum. 3-way number partitioning is known to be NP-hard. Different results have been proved regarding ...
2
votes
0answers
219 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 ...
2
votes
0answers
32 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?
2
votes
0answers
26 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 ...
2
votes
0answers
65 views

Modular reduction in a finite field

Let $\mathbb{F}_p$ be a finite field of prime order $p$. Define $r_q : \mathbb{F}_p \to \mathbb{F}_p$ as $r_q (x) = x \bmod q$ with $q<p$. A tad more formally, treat $x$ as an integer in $[0, p)$ ...
2
votes
0answers
46 views

Theoretical performance measures other than worst case

Suppose that $P \neq NP$, and $P = BPP$. Assume one is given a decision language $L \in NPC$, and she has only polynomial time turing machines. Additionally, she can't use randomness (not sure that's ...
2
votes
0answers
121 views

polynomial time reducibility, if $A \in \mathbf P$ and $B \in \mathbf N$ $\mathbf P \setminus \{\emptyset,\Sigma^*\} $ and vice versa

$f: \Sigma^* \to \Sigma^*$ is a polynomial time computable function if some poly-time Turing Machine M, on every input w, halts with just $f(w)$ on its tape. Language $A$ is polynomial time reducible ...
2
votes
0answers
303 views

Building a poly-time verifier given a poly-time decider

Can I build a polynomial time verifier for problem, given a non-deterministic polynomial time decider for that problem? I assume I should modify the decider such that it will verify the certificate. ...
2
votes
0answers
53 views

Longest cycle, existance of approximate algorithm implies existence of better one

This is an exercise from an old exam that I don't know how to solve. For any undirected graph $G$, let $c(G)$ be the length of the longest (simple) cycle in $G$. Show that if there exists a ...
2
votes
0answers
49 views

Cobham's characterization of FP

Does anyone know of an accessible introduction to Cobham's model independent characterization of FP and it's equivalence to the standard definition using Turing machines? The best source I could find ...
1
vote
0answers
30 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 ...
1
vote
1answer
19 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 ...
1
vote
0answers
40 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
0answers
75 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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
279 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
0answers
38 views

Smallest string containing sets of letters

I am looking for a solution to this problem: Given multiple sets of letters (Set0={a,b,c,d}, Set1={d,e,f,g}, Set2={a,b,e,g}, ...), what is the minimal length of the string containing all the sets. The ...
1
vote
1answer
293 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) ...
1
vote
0answers
59 views

Finding simple min-weight path between two vertices in graph with negative edge weights

Given a weighted graph (negative weights are allowed) and two vertices $u$ and $v$, can we find the simple min-weight path between $u$ and $v$? There can be a negative cycle on the path from $u$ to $v$...
1
vote
0answers
23 views

Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
1
vote
0answers
98 views

What are widely-used, practical applications to come from the study #P problems?

When, beyond theoretical exercises, do we care how many solutions we can find for something? I had an analogous question for TMs before - why is it useful to study machines that can only deliver ...
1
vote
0answers
36 views

Pedagogic reference on cut generating functions

Can you recommend an introduction to the topic of cut generating functions? I am looking for introductory or review-like material. I did find the following survey paper, but it seems to be addressed ...
1
vote
0answers
33 views

Mixing time of three particle systems

Is there anything known about mixing time of Markov chains for three particle systems? It is proved here http://www.ams.org/journals/tran/2005-357-08/S0002-9947-05-03610-X/S0002-9947-05-03610-X.pdf ...
1
vote
0answers
34 views

Is this problem in P: Finding a common key for a collection of systems of equations?

Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all ...
0
votes
0answers
42 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, ...
0
votes
1answer
48 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(...
0
votes
0answers
40 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?
0
votes
0answers
23 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
90 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 ...
0
votes
0answers
53 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 ...
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 ...
0
votes
0answers
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 ...
0
votes
0answers
21 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 ...
0
votes
0answers
49 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 ...
0
votes
0answers
77 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 ...
0
votes
0answers
31 views

Is retrospective inference NP-hard?

Here is a minimal working example of the question: Consider a network with nodes arranged in a pyramid: $1$ node in the first row, $1+d$ nodes in the second, $1+2d$ nodes in the third, and so on, ...
0
votes
0answers
46 views

Is the succinct version of P-complete problems out of P?

Consider the succinct versions of the P-complete problems as a Boolean circuit which represents its input in exponential more succinct ways. Could these succinct versions are in P or out of P?
0
votes
0answers
33 views

USAT, Arora Barak's book

Here on the page 354 Arora and Barak write below the shaded area "but in fact $f(\phi)$ $\notin SAT$" and not "but in fact $f(\phi) \in SAT$" While in the last line of the shaded area they write $...
0
votes
0answers
201 views

Linear time reduction equivalence

I have to show if the following statement is true or false. Suppose we have two problems $A$ and $B$. We want to know whether the following is true: If $A \le_p B$ and there is an algorithm which ...
0
votes
0answers
157 views

Prove that Vertex Cover belongs to NP

How to prove that the problem VERTEX-COVER belongs to $NP$? The problem VC is defined as follow: INSTANCE: Graph $G = (V,E)$ and an integer $k$ PREDICATE: Is there a subset $V_1 \in V $ s.t $\mid V_1 ...
0
votes
0answers
27 views

Revisiting complexity of art gallery-like problem

In a question I had asked earlier, I was interested in knowing whether we could decide in polynomial time whether, for a directed graph $G$ with every one of its vertices belonging to an edge, a size-$...
0
votes
0answers
153 views

Are there any RE-complete languages w.r.t. polynomial reduction?

I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L $, meaning a polynomial-time reduction. I've tried to use $L=A_{TM}$ (the accepting problem), but got ...