# Questions tagged [polynomial-time]

The tag has no usage guidance.

120 questions
Filter by
Sorted by
Tagged with
50 views

### Average case complexity of decision version of NP-hard problem

I am a bit confused regarding the average case complexity of certain graph problems that are NP-hard like graph coloring, clique, dominating set and whose decision version is NP-complete. It is ...
70 views

### distinguishments between query complexity of membership oracles and standard time complexity

Many combinatorial optimization problems can be described as follows. We are given a set system $(E,I)$, where $I \subseteq 2^E$ and a weight function $w: E \rightarrow \mathbb{N}$. The goal is to ...
1 vote
52 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 ...
69 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-...
228 views

105 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 ...
107 views

### Joint Scheduling Problem with Variables Arrival Times

The scheduling problem $1\bigl|r_j\bigl|\Sigma\,U_j$ is strongly NP-hard but when preemption is allowed the scheduling problem $1\bigl|pmtn,r_j\bigl|\Sigma\,U_j$ becomes strongly polynomial. I have a ...
67 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 ...
65 views

### Interpolation to find polynomial multivariate derivative

This question came when reading a paper here about affine projections of polynomials. The publisher claims in Proposition 22 that Let $f(\mathbf{x}) \in F[\mathbf{x}]$ be an $n$-variate polynomial of ...
1 vote
40 views