All Questions
Tagged with co.combinatorics computational-complexity
216 questions
6
votes
3
answers
475
views
Complexity of high-order differentiation
Let $g(x) = \exp(f(x))$. Assuming numerical (or symbolic) values of $f(x), f'(x), f''(x), \ldots, f^{(n)}(x)$ are known, is there a way to compute $g'(x), g''(x), \ldots g^{(n)}(x)$ (or even the ...
- 2,235
2
votes
2
answers
249
views
Indexing schemes of binary sequences
I am looking for "low-complexity" indexing methods to enumerate binary sequences of a given length and a given weight.
Formally, let $T_k^n = \{x_1^n \in \{0,1\}^n: \sum_{i=1}^n x_i = k\}$. How to ...
- 1,839
54
votes
10
answers
8k
views
The "sensitivity" of 2-colorings of the d-dimensional integer lattice
Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate).
Let $C$ be a two-...
- 9,823
13
votes
6
answers
3k
views
A decision problem in graph coloring
It'll be great to get a pointer or answer to the following question:
What is the complexity of the following problem? Given an unweighted and undirected graph, can we have a proper (not necessarily ...
- 261
7
votes
1
answer
357
views
How long are the certificates produced by the Zeilberger and WZ methods for solving combinatorial sums (A=B)?
In the book "A = B" by Petkovesk, Wilf, and Zeilberger, (downloadable here), the authors provide several algorithmic methods for finding closed forms or recurrences for sums involving e.g. binomial ...
- 23k
2
votes
1
answer
353
views
poly-time algorithm to choose elements of sets
Let $A_1,A_2,\ldots,A_k$ be finite sets. Furthermore, for each $i\in\{1,2,\ldots,k\}$, let $B_i$ be a set whose elements are subsets of $A_i$.
Is there any polynomial-time algorithm that decides ...
- 85
10
votes
1
answer
910
views
Finding Two Rainbow Spanning Trees
Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour.
Is the following problem NP-...
- 1,288
12
votes
4
answers
4k
views
reversible Turing machines
Hello,
Let T be a Turing machine such that
1) it operates on the alphabet {0,1},
2) its set of states is A
3) the language it accepts is $L$ .
Does there exists a Turing machine S which also ...
- 3,897
26
votes
6
answers
9k
views
The problem of finding the first digit in Graham's number
Motivation
In this BBC video about infinity they mention Graham's number. In the second part, Graham mentions that "maybe no one will ever know what [the first] digit is". This made me think: Could ...
- 1,593
7
votes
1
answer
805
views
Counting Eulerian Orientation in a 4-regular undirected graph
We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 out-...
6
votes
1
answer
1k
views
Finding a cycle of fixed length in a bipartite graph
Is finding a cycle of fixed even length in a bipartite graph any easier than finding a cycle of fixed even length in a general graph? This question is related to the question on Finding a cycle of ...
- 784
11
votes
1
answer
860
views
Counting colored rook configurations in the cube - when is it even?
Informal Statement
In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a rook in position $(i,j,...
- 1,088
-2
votes
1
answer
519
views
cardinal equivalence: for each boolean formula, |quantifications| = |assignments|. [closed]
Cardinal Equivalence Theorem
For each boolean formula, |quantifications| = |assignments|.
The set of valid quantifications has some cardinality, call that |Q(B)...
6
votes
0
answers
346
views
Enumerating (generalized) de Bruijn tori
Given a cyclic word $w$ of length $N$ over a $q$-ary alphabet and $k \in \mathbb{Z}_+$, consider the directed multigraph $G_k(w) = (V,E)$ with $V \subset$ {$1,\dots,q$}$^k$ given by the $k$-lets (i.e.,...
- 15.4k
29
votes
7
answers
8k
views
Solving NP problems in (usually) Polynomial time?
Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...
- 2,383
7
votes
2
answers
1k
views
How unhelpful is graph minors theorem?
A very interesting Robertson-Seymour (graphs minors) theorem says:
Any infinite collection of graphs $C$ with the property that if $G\in C $ then its minors also are has the form $\{$graphs $G$ ...
- 15.1k