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.

46 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
0answers
285 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
119 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
144 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
140 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
116 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
71 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

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
43 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 ...
2
votes
0answers
57 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
44 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
89 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
241 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
52 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
47 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
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 $\...
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
47 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(...
1
vote
0answers
141 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
22 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
vote
0answers
37 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
210 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
54 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
22 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
35 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
28 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
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 ...
0
votes
1answer
43 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
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 ...
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 ...
0
votes
0answers
32 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
30 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
34 views
0
votes
0answers
28 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
43 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
32 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
139 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
151 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
111 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 ...
0
votes
0answers
674 views

Proving languages are complete on NL?

I'm trying to prove that every language that is not the empty set or {0,1}* is complete for NL (nondeterministic logarithmic space) under polynomial-time Karp reductions. I'm really not sure how to ...
0
votes
0answers
66 views

Nash Equilibrium in Tree of Bounded Degree

I have an exercise which I can't solve. Exercise. Consider a game where the players have $2$ pure strategies each and assume that the graph $G$ is a tree with maximum degree $3$. Give a polynomial ...
-1
votes
1answer
29 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