<p>Given $d&gt;0$ and a complete graph $K_n$ is there an integer $m&lt;d$ such that there is an assignment of vectors from $\Bbb F_2^m$ to every edge such that sum of vectors in every simple cycle is not a $0$ vector? </p>

<p>What is the smallest complexity class does this problem belong to?</p>

CC BY-SA 3.0
2017-03-28T10:11:30.217Z
How is the input encoded? The input essentially consists of two numbers $d$ and $n$. Are they given in unary or binary? Moreover, for every $n$, there is a $d(n)$ such that the answer is $0$ for all $(\delta,n)$ with $\delta < d(n)$ and $1$ for all with $\delta \ge d(n)$.
Markus Bläser
CC BY-SA 3.0
2017-03-28T10:16:39.510Z
@MarkusBläser What is smallest class if input is unary and what if it is binary (excellent comment though)? $d(n)$ exists is clear.
Turbo
CC BY-SA 3.0
2017-03-28T10:44:26.320Z
You should first figure out what $d(n)$ is, and only then worry about its complexity. Quite possibly it may given by a simple closed-form which would make it trivial to compute. As far as I can see, it is even possible that $d(n)$ is eventually *constant*: after all, $d=1$ is enough for *odd* cycles.
Emil Jeřábek
CC BY-SA 3.0
2017-03-28T10:47:54.073Z
@EmilJeřábek finding $d(n)$ is what motivated me to this query. I know $(\log n)^2<d(n)<n\log n$ but pinning down it further looks hard
Turbo
CC BY-SA 3.0
2017-03-28T12:58:56.677Z
d(n) is recently proved to be linear in n. See https://arxiv.org/abs/1702.05773
saisandeep
<complexity-classes><polynomial-hierarchy>
What is the smallest complexity class that this problem belongs to?
Turbo
# What is the smallest complexity class that this problem belongs to?

(Asked by: username_0 on 2017-03-28)

Given $d>0$ and a complete graph $K\_n$ is there an integer $m

What is the smallest complexity class does this problem belong to?

**Tags:** complexity-classes, polynomial-hierarchy
> **Comments:**
> **username_1**: How is the input encoded? The input essentially consists of two numbers $d$ and $n$. Are they given in unary or binary? Moreover, for every $n$, there is a $d(n)$ such that the answer is $0$ for all $(\delta,n)$ with $\delta < d(n)$ and $1$ for all with $\delta \ge d(n)$.  
> **username_0**: @MarkusBläser What is smallest class if input is unary and what if it is binary (excellent comment though)? $d(n)$ exists is clear.  
> **username_2**: You should first figure out what $d(n)$ is, and only then worry about its complexity. Quite possibly it may given by a simple closed-form which would make it trivial to compute. As far as I can see, it is even possible that $d(n)$ is eventually *constant*: after all, $d=1$ is enough for *odd* cycles.  
> **username_0**: @EmilJeřábek finding $d(n)$ is what motivated me to this query. I know $(\log n)^2<d(n)<n\log n$ but pinning down it further looks hard  
> **username_3**: d(n) is recently proved to be linear in n. See https://arxiv.org/abs/1702.05773  

---

## 0 answers

