Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
Turbo's user avatar
  • 13.9k
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 ...
econ's user avatar
  • 1
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 ...
Mohammad Al-Turkistany's user avatar
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 ...
Tippisum's user avatar
  • 153
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 ...
Turbo's user avatar
  • 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]$ ...
Turbo's user avatar
  • 13.9k
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 ...
borekking's user avatar
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 ...
user499408's user avatar
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 ...
Doriano Brogioli's user avatar
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 ...
Doriano Brogioli's user avatar
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 ...
Arnold Neumaier's user avatar
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 ...
Alexandr Dorofeev's user avatar
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 ...
user1642683's user avatar
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$. ...
Igor Pak's user avatar
  • 17k
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 &...
Rebecca J. Stones's user avatar
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 ...
Valentin Brimkov's user avatar
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 ...
The Amplitwist's user avatar
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 ...
cbyh's user avatar
  • 143
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)...
Dattier's user avatar
  • 4,074
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$...
Penelope Benenati's user avatar
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 ...
Alm's user avatar
  • 1,207
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 ...
Turbo's user avatar
  • 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 ...
Michał Oszmaniec's user avatar
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 ...
Bill Bradley's user avatar
  • 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 ...
Martin Rubey's user avatar
  • 5,822
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 ...
joro's user avatar
  • 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 ...
plegri's user avatar
  • 21
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 ...
Ben Tom's user avatar
  • 107
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)$ ...
lisi's user avatar
  • 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\\...
Tippisum's user avatar
  • 153
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 ...
Turbo's user avatar
  • 13.9k
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 ...
joro's user avatar
  • 25.4k
3 votes
0 answers
132 views

Can equality of chromatic symmetric functions of two trees be checked in polynomial time?

Stanley defined chromatic symmetric functions (CSF) in 1995 (Advances in Math) where he conjectured that trees can be distinguished by their CSF. However, tree isomorphism is decidable in P (...
Bishal Deb's user avatar
2 votes
0 answers
70 views

Isomorphism preserving transformation graph to graph of logarithmic boolean width and bounded degeneracy

The paper On graph classes with logarithmic boolean-width claims that some graph problems are fixed parameter tractable with parameter the boolean width. In particular, boolean-width of the complement ...
joro's user avatar
  • 25.4k
5 votes
1 answer
276 views

NP-hardness of a sequence problem

Given $n$ binary sequences $s_i$ ($1\le i\le n$) with common period $T$. Let $s_i^{t_i}$ denote the sequence obtained by cyclically shifting $s_i$ for $t_i$ bits. The $n$ sequences form a good system ...
lchen's user avatar
  • 367
1 vote
0 answers
147 views

The chromatic polynomial of a line graph

Is there a way to obtain the chromatic polynomial of the line graph of a regular simple graph, having known the chromatic polynomial of the graph? There already exist characterizations of line graph ...
vidyarthi's user avatar
  • 2,089
0 votes
1 answer
147 views

Complexity of edge coloring of class 1 graphs

We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it ...
vidyarthi's user avatar
  • 2,089
2 votes
0 answers
81 views

Number of solutions to linear diophantine equations, with natural coefficients in a box

Let c, k, d $ \in \mathbb{N} $, let a, x $ \in \mathbb{N}^k $ suppose for all i $ \leq $ k, $ x_i \leq d $, $ a_i \in \mathcal{O}(d2^i) $ and $ \sum{a_ix_i} = c $ my question is for the value of c ...
Avi Tachna-Fram's user avatar
3 votes
1 answer
96 views

What is known about computing all binary error correcting codes of given parameters?

Define a binary $(n, M, 2e + 1)$ code to be a code $C$ having $M$ code words in $\mathbb{F}_2^n$ whose minimum distance is $2e + 1$. Are there any sources about using algorithms to find all given ...
J P's user avatar
  • 143
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$ ...
Polaris's user avatar
  • 111
5 votes
0 answers
301 views

The expressiveness of functions computable on trees

Motivation: Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary ...
Aidan Rocke's user avatar
  • 3,871
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? ...
joro's user avatar
  • 25.4k
2 votes
0 answers
62 views

A combinatorial question about encoding the subsets of logarithmic-bounded cardinality

Let $k \in \mathbb N - \{0\}$ and $f(n) = \binom n 0 + \binom n 1 + \dotsc + \binom n {\log^k n}$. Our question is: $f(n) = o(2^{\log^{k+1} \ (n)})$ or $f(n) = \Theta(2^{\log^{k+1} \ (n)})$, which ...
Arthur Kexu-Wang's user avatar
1 vote
0 answers
45 views

Coloration of an interval graph with constraints [closed]

Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
user147149's user avatar
3 votes
1 answer
182 views

Edge coloring graphs is in P?

It is known that there exist polynomial time algorithm to approximate the Lovasz number or the supremum of Shannon capacity of graphs. By Vizing's theorem, the graph $G$ has only two chromatic ...
vidyarthi's user avatar
  • 2,089
4 votes
1 answer
166 views

Complementing the red and blue boolean cube?

Given a boolean $0/1$ cube in $n$ dimensions with $2^{n-1}$ red and $2^{n-1}$ blue points can we complement the cube (blue becomes red and vice versa) in $\operatorname{poly}(n)$ transformations? ...
Turbo's user avatar
  • 13.9k
0 votes
0 answers
82 views

Proving Vizing's and Brooks' theorem using the polynomial approach

It is known that the graph polynomial defined by $\prod_{i<j}(x_i-x_j)$ where the vertices $x_k\ \ , \ \ k=\{1,2\ldots,n\}$ are ordered with respect to some order; can be used to verify the proper ...
vidyarthi's user avatar
  • 2,089
5 votes
1 answer
214 views

Graphs with Hermitian Unitary Edge Weights

Very recently, Hao Huang proved the Sensitivity Conjecture, which had been open for 30 years or so. Huang's proof is surprisingly short and easy. Here is Huang's preprint, a discussion on Scott ...
3 votes
2 answers
235 views

Strong chromatic index of some cubic graphs

Edit 2019 June 26 New computer evidence forces us to revise our guesses relating strong chromatic index and girth Edit 2019 June 25 Some mistakes have been corrected. Question 2 has changed. ...
EGME's user avatar
  • 1,018
2 votes
1 answer
140 views

Matrix completion problem with determinant condition?

Given two $\{0,1\}^{n\times n}$ matrices $L$ and $M$ and an integer $m$ is there a polynomial in $n$ algorithm to find a $\{-1,0,+1\}$ matrix $T$ such that $$\mathsf{det}(L+T\odot M)=m$$ where $\odot$ ...
Turbo's user avatar
  • 13.9k

1
2 3 4 5