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.
36
votes
Accepted
Can one measure the infeasibility of four color proofs?
To answer the question it is important to disentangle the proof as follows.
Theorem 1. Every minimum counterexample to the 4CT is an internally 6-connected triangulation.
Theorem 2. If $T$ is a min …
- 32.1k
28
votes
Can a problem be simultaneously polynomial time and undecidable?
As others have mentioned, the answer to your title question is strictly speaking no. With regards to your other questions, it has been proven that it is undecidable to compute the excluded minors for …
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
11
votes
Accepted
Minimum number of edges to remove to have low degree
If you also insist that the bounded-degree subgraph is connected, then your problem is NP-Hard, since it includes the Longest Path problem when $k=2$.
On the other hand, without the connectivity cons …
- 32.1k
9
votes
Accepted
A minimum set hitting every base of a matroid
The problem is hard in general. Note that a minimal set that intersects every base of a matroid $M$ is a dependent set in the dual matroid $M^{*}$. Such sets are called cocircuits. So, you are look …
- 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
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
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
6
votes
Efficient Hamiltonian cycle algorithms for graph classes
One class of graphs for which many NP-hard problems (including finding a Hamiltonian cycle) are easy (linear-time) are graphs of bounded tree-width. Indeed, by Courcelle's theorem any problem which c …
- 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
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
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
4
votes
Is this strange problem NP-complete?
Here's an idea (not a solution), which I thought I would post before heading out for coffee inspiration.
Let $f(x)=\sum_{i=1}^n p_i(x)$ be the expression we are attempting to simplify. One possible …
- 32.1k