All Questions
Tagged with co.combinatorics computational-complexity
216 questions
1
vote
0
answers
92
views
Proof for non-existence of short integer program for squares
We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question.
Is there a way to show within an ...
- 13.9k
19
votes
2
answers
1k
views
Explicit invariant of tensors nonvanishing on the diagonal
The group $SL_n \times SL_n \times SL_n$ acts naturally on the vector space $\mathbb C^n \otimes \mathbb C^n \otimes \mathbb C^n$ and has a rather large ring of polynomial invariants. The element $$\...
0
votes
0
answers
92
views
Algorithm that can solve or approximate the solution to a combination problem
I have a computational problem on my hands and I would like your help.
Here is my problem (simplified)
Let $X = \{x_1, x_2, \ldots, x_n\}$ represent a set of $n$ values.
Each value $x_i$ has a ...
- 869
3
votes
1
answer
342
views
counting patterns in a word
Do algorithms exist to find all the patterns in a word?
I would like to count all the 3-step increasing sequences (123 i.e. 123, 234 & 345) in some word in the alphabet {1,2,3,4,5}
such as "...
- 1,446
4
votes
0
answers
155
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
- 2,993
14
votes
6
answers
4k
views
Non-constructive proofs vs. efficient algorithms
My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity.
The wikipedia article on constructive proof begins, "a constructive ...
- 1,446
2
votes
0
answers
81
views
Degeneracy and the "Linear Degeneracy Testing" problem
The Affine Degeneracy problem is about deciding whether $n$ given points in $\mathbb{R}^d$ (or $\mathbb{Q}^d$) are "in general position". i.e. there is no $d+1$ tuple of points which lies in ...
- 153
3
votes
1
answer
214
views
NP-hardness of finding maximum of minimum element in diagonal of a matrix
For $A = \{a_{ij}\} \in R^{n\times n}$, is finding
$$
\max_{\sigma \in S_n}\min_{1 \le i \le n} a_{i,\ \sigma_i}
$$
NP-hard?
- 32.1k
5
votes
1
answer
291
views
Minimum number of edges to remove to have low degree
I have the following problem, where $k$ is a fixed integer.
Input: Graph $G$.
Output: Minimum number of edges to remove from $G$ to obtain a graph such that every node has degree at most $k$.
Do ...
- 32.1k
1
vote
0
answers
101
views
On determinant and permanent of certain homotopy defined simple matrices
Let $A_1,A_2,B_1,B_2$ be four $n\times n$ $0/1$ square matrices where $$\det(A_1)=\det(A_2)=per(A_1)=per(A_2)=1$$
$$\det(B_1)=\det(B_2)=per(B_1)=per(B_2)=0$$
hold ($per$ refers to permanent).
I. What ...
- 13.9k
1
vote
0
answers
161
views
On an optimization question
Suppose we have a square matrix $M=(1-z)A+zB$ where $A,B$ have integer entries from $\{0,1\}$ with $\det(A)+\det(B)=1$ and $\det(A),\det(B),per(A),per(B)\in\{0,1\}$ and we want to find $z\in[0,1]$ ...
- 13.9k
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 ...
- 1,446
3
votes
2
answers
404
views
A natural problem on "cartesian union" of set families (hypergraphs). Are there NP-complete problems related to the notion of cartesian product?
I'm curious whether the problem below is NP-complete.
I provide two simple definitions and one example at first.
Definition 1.
Let $\langle \cal S_i\rangle\substack{i\in I}$ and $\langle \cal S_j \...
54
votes
2
answers
8k
views
Walsh Fourier transform of the Möbius function
This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly orthogonal to Morse
August Ferdinand Möbius (November 17, 1790 – ...
- 1,446
2
votes
0
answers
245
views
Pancake sorting problem – Is computing f(n) NP-hard?
The so-called Pancake flipping problem first discussed by Jacob E. Goodman here yields two entangled problems:
MIN-SBPR (Sorting By Prefix Reversals) - Given a permutation, find the smallest sequence ...
- 51
0
votes
0
answers
59
views
NC0 randomness vs. non-uniformity
In
Ajtai and Ben-Or. A theorem on probabilistic constant depth
Computations. STOC '84, 1984
Ajtai and Ben-Or show a non-uniform derandomization of BPAC0.
Is there a similar relation known for ...
- 869
3
votes
1
answer
271
views
The number of $3$-CNF formulas in $n$-variables and the fraction of satisfiable ones
What is the number of $3$-CNF (conjunctive normal form) formulas with $n$ sentential variables and what is the fraction of satisfiable ones? I consider two formulas the same if they are syntactically ...
- 32.1k
2
votes
1
answer
209
views
Computational complexity and commuting functions, examples and conjectures
History of the question. I was proposing a conjecture here, called Prop. 1. Fedor Pakhomov showed a counter-example. Here I am proposing a slightly weaker version of the conjecture, Prop. 2, that ...
- 5,831
8
votes
1
answer
225
views
Computational complexity and commuting functions
EDIT: in this question, I was proposing a conjecture, Prop. 1. Fedor Pakhomov showed a counter-example. In this new question I propose a slightly weaker conjecture that holds even for that example and ...
- 469
4
votes
1
answer
362
views
Lower bound on the number of solutions of 2SAT
To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...
- 83
1
vote
1
answer
187
views
A combinatorial matrix reconstruction problem II
For a positive integer $n$, let an $n$-shuffle be a multiset
$S=[(S_i,d_i)|i=1,\ldots,n]$ of pairs $(S_i,d_i)$, where each
$S_i$ is a multiset of $n$ numbers containing the number $d_i$.
A realization ...
- 3,873
1
vote
1
answer
209
views
Deciding if given number is a permanent of matrix
The permanent of an $n$-by- $n$ matrix $A=\left(a_{i j}\right)$ is defined as
$$
\operatorname{perm}(A)=\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)}
$$
The sum here extends over all ...
- 47.3k
11
votes
1
answer
410
views
Complexity of counting regions in hyperplane arrangements
Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$.
...
3
votes
0
answers
130
views
Is counting Latin squares #P-complete?
I feel like I should know the answer to this. I did some Googling and didn't easily find the answer...
Question: Is counting Latin squares #P-complete?
Obviously the corresponding decision problem &...
- 1,327
11
votes
3
answers
3k
views
Do you know a faster algorithm to color planar graphs?
while studying the four color theorem, I implemented an algorithm (in Python and Sage) that can color planar graphs much faster than the implementations I found around on internet.
The program can be ...
- 51
1
vote
1
answer
119
views
Problem NP-completeness on a specific graph class
Consider the class of simple connected n/2-regular graphs, n even. Are the maximum clique problem and/or maximum independent set problem NP-complete on such graphs? Is there any known result which ...
- 9,501
10
votes
1
answer
890
views
How hard is it to compute the Davenport constant?
The Davenport constant $D(G)$ of a finite abelian group $(G,+)$ is the least positive integer $k$ such that every sequence in $G$ of length $k$ has a zero-sum (nonempty) subsequence.
It seems that the ...
- 188k
0
votes
0
answers
84
views
Shattering of a set of binary classifiers
Let $S$ be a set, and let $\mathcal{F}_{S}=\{f:S\to\{-1,+1\}\}$ be a set of different label assignments. Show that $\mathcal{F}_{S}$ shatters at least $|\mathcal{F}_{S}|$ subsets of $S$.
Here is what ...
- 143
10
votes
0
answers
454
views
Fast method to verify if a point belongs to a given convex $d$-polytope
We are given a $d$-dimensional convex polytope $P\in\mathbb{R}^d$. Assume we have all the supporting hyperplanes describing $P$ and its vertices. Let $S$ be a sequence of $n\gg 1$ points $\mathbb{R}^d$...
- 1,677
22
votes
2
answers
6k
views
$\mathbf{P} = \mathbf{NP}$, what's the problem?
Let's take the problem of the backpack: $A_1,\ldots ,A_n$ the weights that are integers, and we want to know if we can achieve a total weight of $V$.
We take $$I=\dfrac{1}{2\pi}\int_0^{2\pi} \exp(-iVt)...
- 2,912
2
votes
0
answers
91
views
Blind construction of planar graph with additive spanning tree count
Suppose we have two planar graphs $G_1$ and $G_2$ with number of spanning tree count $P_1$ and $P_2$ respectively then there is an easy construction which gives a planar graph with spanning tree count ...
- 13.9k
7
votes
0
answers
203
views
Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs
Let $G=(V,E)$ be a graph with an even number of vertices $|V|=2n$. Assume that $G$ is $K_{3,3}$-free i.e. it does not contain a graph isomorphic to biclique $K_{3,3}$. A perfect matching of $G$ is a ...
- 63.9k
1
vote
1
answer
137
views
Complexity of edge coloring graphs with $\Delta(G) \ge n/3$ assuming the overfull conjecture
Closely related to this on cstheory.
Let $G$ be graph of order $n$ with $\Delta(G) \ge n/3$.
Assume the overfull conjecture.
Can we edge color $G$ with minimal number of colors in polynomial time?
...
CommunityBot
- 1
8
votes
0
answers
237
views
Size of 3-SAT assignments
Let $F(N,M)$ be the set of 3-SAT formula with $N$ variables and $M$ clauses. For a given formula $f\in F(N,M)$, we can ask for the set $s_f$ of truth assignments that satisfy $f$. (If $f$ is ...
- 3,979
4
votes
0
answers
182
views
Determine the minimal elements of a Dynkin system generated by a finite set of finite sets
(This is a refined version of https://cs.stackexchange.com/q/144371)
Let $\Omega$ be a finite set. A Dynkin system on $\Omega$ is a subset of the power set of $\Omega$ containing $\Omega$, which is ...
- 5,822
13
votes
1
answer
2k
views
Erdős multiplication problem revisited
This is a well-known problem and is about counting the number of distinct numbers in the $n \times n$ multiplication table.
The very problem has been discussed in-depth and, as such, I require no ...
- 32.1k
47
votes
7
answers
5k
views
Is it easy to produce hard-to-color graphs?
This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
1
vote
0
answers
185
views
Maximum independent set in dense graphs
Let $0 < A < 1$ and $G$ be connected d-regular graph
with degree $d=[A n]$. The density of $G$ is about $A$.
Q1 Are there constraints on $A$ such that finding maximum
independent set of $G$ is ...
- 25.4k
2
votes
0
answers
64
views
Polynomial-time algorithm for uniformly sampling the $n$-slice of a context-free language
Let $L\subset \Sigma^*$ be a context-free language. The $n$-slice is the intersection $L\cap \Sigma^n$ for a non-negative integer $n$.
Is there a polynomial-time algorithm for uniformly sampling from ...
- 3,065
24
votes
2
answers
2k
views
Can one measure the infeasibility of four color proofs?
Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...
- 32.1k
1
vote
1
answer
218
views
What is this invariant graph?
Let $G$ be a simple graph (finite or infinite), $[n]\mathrel{:=}\{1,...,n\}$. Define the function:
$$\varepsilon_n(G)\mathrel{:=}\min_\phi{\lvert{\operatorname{dom} (\phi)}\rvert},$$
where $\phi$ is ...
- 7,226
46
votes
8
answers
5k
views
Can a problem be simultaneously polynomial time and undecidable?
The Robertson-Seymour theorem on graph minors leads to some interesting conundrums.
The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As ...
- 32.1k
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 ...
- 236k
1
vote
0
answers
75
views
Subgraph isomorphism problem with linear map
I am working on proving the NP-hardness of a problem by reducing it from the subgraph isomorphism problem. Currently, I can reduce it from the following problem:
Problem 1: Given two graphs $G=(V, E)$ ...
- 101
4
votes
1
answer
209
views
Finding a binary variable assignment to make a matrix with variables singular (over F_p)
Consider a square matrix defined over a finite field $M\in\mathbb{F}_p^{n\times n}$ having the following form
$$M=\begin{bmatrix}a_{11}+b_{11}x_1&a_{12}+b_{12}x_1&\dots&a_{1n}+b_{1n}x_1\\...
- 14k
1
vote
0
answers
209
views
Solution to system of linear equations
Input: System of linear equations $$A[x_1,\dots,x_{t}]=b$$ where number of equations is at least number of variables but independence is not guaranteed. However there is atmost one non-negative ...
- 13.9k
25
votes
2
answers
2k
views
Who first dubbed them "expander graphs"?
Expander graphs
("sparse graphs that have strong connectivity properties")
burst onto the mathematical scene around the millennium, but I have not
been successful in tracing the origin of
(a) the ...
- 91
29
votes
2
answers
1k
views
Determining if a rational function has a subtraction-free expression
This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class.
Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...
- 91.8k
1
vote
1
answer
157
views
Is the graph minicut with the node cardinality constraint NP-hard?
I wonder whether the following problem is a well-studied NP-hard problem?
Get a graph $G$ and a number $k$, we partition the graph $G$ into two components where each component should have at most $k$ ...
CommunityBot
- 1
1
vote
0
answers
176
views
Reduction graph isomorphism to maximum independent set in very dense graph
We got a reduction graph isomorphism to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G,H$ be graphs of order $n$ and adjacency ...
- 25.4k