Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with computational-complexity
Search options not deleted
user 2233
This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Komolgorov Complexity and so on.
5
votes
Accepted
Approximation of Hamiltonian cycles
Claim. For every $\rho \geq 1$, there is no polynomial $\rho$-approximation algorithm for $\texttt{MinHalfSimpCycle}$, unless P=NP.
Proof. Let $G$ be an instance of the Travelling Salesman Problem (TS …
- 32.1k
2
votes
Is it NP-hard to find the min set of nodes in a graph so that the set of paths joining them ...
The problem is indeed NP-hard, and cannot even be well-approximated in polynomial time. To see this, consider an instance $(\mathcal{F}, V)$ of the set cover problem. We construct an instance of the …
- 32.1k
5
votes
Accepted
The number of $3$-CNF formulas in $n$-variables and the fraction of satisfiable ones
Regarding the fraction of satisfiable 3-CNF formulas in $n$ variables, it is widely believed that there is a phase transition that occurs depending on how many clauses there are compared to the number …
- 32.1k
8
votes
Erdős multiplication problem revisited
The answer to both your questions are (essentially) yes, and are given in a recent paper of Brent, Pomerance, Purdum, and Webster.
Regarding (b), they show that $A(n)$ can be computed in subquadratic …
- 32.1k
7
votes
Metric TSP with integer edge cost
No polynomial-time algorithm exists, unless P=NP.
Indeed, even for TSP instances where all distances are $1$ or $2$ (note that these automatically satisfy the triangle inequality), Engebretsen and Kar …
- 32.1k
2
votes
Accepted
One part of a bipartite graph has max degree 3. Partition the other part to 3 ~equal subsets...
Let $G=(U,V,E)$ be a bipartite graph where $U=[n], V=\binom{[n]}{3}$, and there is an edge between $u \in U$ and $v \in V$ if and only if $u \in v$. Then $\deg(u)=\binom{n-1}{2}$ for all $u \in V$ an …
- 32.1k
1
vote
Examples of Super-polynomial time algorithmic/induction proofs?
Another example is the matroid intersection theorem, which is a rich source of min/max theorems in combinatorial optimzation. For example, it includes your example (Kőnig's theorem) as a special case …
- 32.1k
19
votes
Accepted
Lagrange four-squares theorem --- deterministic complexity
As far as I know, this is still an open problem. This is discussed in Section $5$ of the paper Finding the four squares in Lagrange's theorem by Pollack and Treviño. They mention that there is a det …
- 32.1k
2
votes
Accepted
3-Approximation Algorithm for 3-Hitting Set
Let $\mathcal{H}$ be a hypergraph where each hyperedge has size $3$. A vertex cover is a set of vertices $X$ such that every hyperedge is incident to a vertex in $X$. Rephrased, our goal is to find …
- 32.1k
3
votes
Accepted
Reconstructing a graph from shortest paths information
This problem is solvable in polynomial-time. Given a $V \times V$ distance matrix $A$, let $G$ be the graph with vertex set $V$, where $uw \in E(G)$ if and only if $A_{uw}=1$. Note that $G$ is the …
- 32.1k
8
votes
Variation on the Subset Sum Problem
I believe your problem is indeed NP-hard, via the following reduction from subset sum. Let $(a_i)_{i=1}^n$ be an instance of SUBSET SUM. We will make an instance of SMALLEST SUBSET SUM as follows. L …
- 32.1k
1
vote
Maximum subgraph edge distance greater than given number
Your problem is not polynomial (unless P=NP), because your problem is polynomially equivalent to maximum independent set, which is NP-hard.
In one direction, given an edge-weighted graph $G$ and a …
- 32.1k
4
votes
Accepted
Construction of planar embedding
Here are some more details. We will prove the following stronger claim.
Theorem. Let $G$ be a planar graph with $n$ vertices and maximum degree 4. For every planar embedding $\Gamma$ of $G$, there …
- 32.1k
4
votes
Graph classes where finding explicit coloring have certificate that it is minumum
One possible answer is the class of all $3$-chromatic graphs. That is, suppose I tell you that your input graph $G$ is $3$-chromatic and I ask you to find an optimal colouring. Evidently, every $3$- …
- 32.1k
7
votes
Accepted
NP-hardness of finding maximum of minimum element in diagonal of a matrix
This seems to be polynomial. Here is a proof. It will be convenient to regard $A$ as an edge-weighted complete bipartite graph $G$. Let $m_1 < \dots < m_\ell$ be the list of edge weights of $G$, le …
- 32.1k