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.
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
1
vote
Deciding whether a given graph has an f-factor or not!
There is also this recent paper of Meijer, Núñez-Rodríguez and Rappaport which gives a polynomial-time algorithm in the case that $f$ is identically $k$ for some fixed $k$. Interestingly, Meijer, Núñ …
- 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
0
votes
Where is it shown how to construct a decomposition tree for a series-parallel graph in linea...
This answer might be slightly overkill (and possibly underkill), but here goes. For any fixed constant $k$, there is a linear-time algorithm to recognize if a graph $G$ has tree-width at most $k$, an …
- 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
Accepted
how to reduce 3-colorable graph to this?
This problem is indeed NP-complete and was in fact one of Karp's 21 NP-complete problems. Googling exact cover will lead to enlightenment.
- 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
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
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
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
2
votes
A certain instance of the Set Covering problem
For the variant that $\mathcal{P}$ consists of all paths, the problem is equivalent to minimum vertex cover, and hence is NP-complete. To see this, I assume that single vertices do not count as paths …
- 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
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
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