Skip to main content
The 2024 Developer Survey results are live! See the results

# Questions tagged [polynomial-time]

The tag has no usage guidance.

39 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
16 votes
0 answers
503 views

### a geometric variant of k-medians. NP-hard or in P?

The following problem is a special case of k-medians. Is it NP-hard? Is it in P? Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$. Output: a set ...
• 10.9k
10 votes
0 answers
228 views

### On Courcelle's question about Monadic second-order logic with cardinality predicates

I have found the following question at openproblemgarden.org: The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the ...
• 2,013
10 votes
0 answers
174 views

• 3,956
4 votes
0 answers
316 views

• 1,072
2 votes
0 answers
88 views

### Minimizing a submodular function containing summation and production under partition matroid constraint

I'm having difficulty solving the following problem: We're given $n$ sets $X_1,\ldots, X_n$. Each set $X_i=\{(a_i,b_i)\}$ contains poly(n) many ordered pairs of non-negatives with $0\le a_i+b_i\le 1$. ...
• 483
2 votes
0 answers
74 views

### Resource bounded Kolmogorov complexity hardness on average over a non uniform distribution of inputs

$K^{poly}$, as well as other related problems such as $MCSP$, is believed to be hard on average [1, 2] when the input is sampled from a uniform distribution (since otherwise one way functions, pseudo-...
• 187
2 votes
0 answers
121 views

### Computing real numbers with Turing Machines

Consider the following decision problem: Given a two integers $n$ and $k$, decide whether $k=\lfloor n\pi\rfloor$ Question: Is this problem known to be in $P$? Although this may look like a stupid ...
• 475
2 votes
0 answers
92 views

### Is there a natural problem in P but no polynomial time algorithm is known?

Most of the time, a problem is shown to be in P by the construction of a polynomial time algorithm. I wonder if there is a natural problem that was proved in P but no explicit algorithm was known? I'm ...
2 votes
0 answers
107 views

### Prize Box Ordering Problem With Position Constraints: Easy or Hard

I have a problem where we have $n$ boxes, each box $i$ have probability $p_i$ of containing a prize with value $h_i > 0$, and remaining probability of containing nothing. Now we are asked to order ...
2 votes
0 answers
72 views

### Is there a poly-time algorithm to compute the drawing of a simple graph (need not be planar) in a 2D-plane such that any two edges cross at most once?

Does there exists a ploynomial time algorithm to embed a simple graph(need not be planar) in a plane satisfying the following conditions? No edge touches vertices other than its end vertices. At any ...
2 votes
0 answers
214 views

### Simultaneous evidence for $L\neq NL$ and $P\neq NP$

We believe $L\neq NL$ and $P\neq NP$. Is there any evidence which simultaneously imply $L\neq NL$ and $P\neq NP$?
• 13.1k
2 votes
0 answers
113 views

### How to prove a general convex set is nonempty or empty in polynomial time?

The general convex set should be represented by a set of (generalized) inequalities $f_{i}(x)\leq 0$ with $f_{i}(x)$ being convex in $x$. I know ellipsoid method and interior method, but I do ...
• 31
2 votes
0 answers
74 views

### Complexity of comparing extended integer power towers

Inspired by this stackexchange question, is it an open problem to compare two power towers of positive integers if we additionally allow numbers lower in the tower to themselves be represented by ...
• 653
2 votes
0 answers
136 views

### On $\Sigma \Pi \Sigma \Pi(2,r)$-circuits

As I understand from the survey "Progress on Polynomial Identity Testing - II" a polynomial-time algorithm for solving PIT for $\Sigma \Pi \Sigma \Pi (2, r)$ is unknown. However, there exists paper ...
• 2,013
2 votes
0 answers
116 views

1 vote
0 answers
55 views

### Find linear combination with small support

Let $v_1,\dots,v_n$ be a basis of a vector subspace of $\Bbbk^N$, say for $\Bbbk$ a finite field. I would like an algorithm to find a linear combination of the $v_i$'s with small support, i.e. with ...
• 191
1 vote
0 answers
46 views

• 13.1k
0 votes
1 answer
225 views

### list of 3-CNF formula that can be solved in polynomial time

Suppose i want to program a 3-SAT solver. I want my solver to first check whether a formula is in the list of 3-CNF that currently known can be solved in polynomial time before resorting to brute ...
• 101