<p><strong>Update:</strong> Sadly, it seems that my initial idea (see below) was incorrect, but it led to some fruitful discussion in the comments.  As a result, the question is still open.</p>
<p>Please let me know if you have any ideas.  :)</p>
<hr />
<p><strong>Initial Idea:</strong> One way to solve Triangle Finding is to find all pairs of vertices that are connected by a path of length 2.  Then, you check if there is an edge between any of these pairs.</p>
<p>A standard way to compute all pairs of vertices that are connected by a path of length 2 is to square the adjacency matrix of the graph.  We can perform Boolean matrix multiplication for the squaring.  All of the 1's in the result will represent pairs of vertices that are connected by a path of length 2.</p>
<p>With nondeterminism, we can compute Boolean matrix multiplication of two n by n matrices in <span class="math-container">$\tilde{O}(n^2)$</span> time by guessing the witness for Boolean matrix multiplication (the concept of witness for Boolean matrix multiplication has been discussed in [1] <a href="https://doi.org/10.1007/s00453-012-9742-3" rel="nofollow noreferrer">https://doi.org/10.1007/s00453-012-9742-3</a> and [2] <a href="https://doi.org/10.1109/SFCS.1992.267748" rel="nofollow noreferrer">https://doi.org/10.1109/SFCS.1992.267748</a>).  Finally, we check in <span class="math-container">$O(n^2)$</span> time if all of the pairs of vertices do not form edges.  <strong>&lt;- This paragraph doesn't quite work.</strong></p>

CC BY-SA 4.0
2021-02-19T06:13:13.630Z
Hi Michael, I don't see how the two references you cite solve the problem. Suppose you guess the output of matrix multiplication. For those output entries which are 1, yes you can guess witnesses. How do you prove the 0 entries are correct, nondeterministically, in approximately n^2 time? You have to prove there is *no* witness in the matrix squaring for all 1-entries in the adjacency matrix, this is what you would need to prove there is no triangle.
Ryan Williams
CC BY-SA 4.0
2021-02-19T07:50:45.690Z
Thank you for your comment!  The references define the concept of witness for Boolean matrix multiplication.  I cited them only to provide background on this concept.
Michael Wehar
CC BY-SA 4.0
2021-02-19T07:53:48.817Z
I think that you made a good point.  The witness for Boolean matrix multiplication may only help identify entries that should be 1's.  Let me think about this more.
Michael Wehar
CC BY-SA 4.0
2021-02-19T08:43:50.567Z
Looking at this again, you would need a for all quantifier to check the 0's efficiently.  In other words, we can guess and check a witness for Boolean matrix multiplication with a $\Sigma_2 TIME(\tilde{O}(n^2))$ machine which might still be interesting.  But, as far as I can tell, we don't seem to get triangle finding in $coNTIME(\tilde{O}(n^2))$.  I will update my incomplete / flawed answer tomorrow.
Michael Wehar
CC BY-SA 4.0
2021-02-19T14:07:54.050Z
I know there is a Merlin Arthur protocol for proving there are no triangles running in close to linear time (in the number of edges), but I don't know a nondeterministic algorithm. It is an interesting problem! In the literature the related problem of matrix multiplication verification has been studied. (If you could verify a matrix mult in n^2 time, even with nondeterminism, you would be done.) One can verify a matrix mult quickly with randomness, this is known as Freivalds's checker. But I don't know how to do it with nondeterminism.
Ryan Williams
CC BY-SA 4.0
2021-02-16T13:55:31.033Z
2021-02-19T19:22:41.580Z
2021-02-19T19:22:41.580Z
Michael Wehar
<p>The Triangle Finding decision problem asks whether there exists a triangle in a graph <span class="math-container">$G$</span> containing <span class="math-container">$n$</span> vertices.  A triangle is a triple of vertices <span class="math-container">$(a, b, c)$</span> such that <span class="math-container">$a$</span> is adjacent to <span class="math-container">$b$</span>, <span class="math-container">$b$</span> is adjacent to <span class="math-container">$c$</span>, and <span class="math-container">$c$</span> is adjacent to <span class="math-container">$a$</span>.</p>
<p>It is known that Triangle Finding is closely related to Boolean matrix multiplication and that Triangle Finding is deterministically solvable in <span class="math-container">$O(n^{\omega})$</span> time where <span class="math-container">$\omega$</span> is the matrix multiplication exponent.  Also, it is known that <span class="math-container">$\omega &lt; 2.373$</span>.</p>
<p><strong>My Question:</strong> Is the complement of Triangle Finding solvable more efficiently with nondeterminism?  In particular, is Triangle Finding in <span class="math-container">$coNTIME(\tilde{O}(n^2))$</span>?  If this is not known, would there be any interesting implications if it was true?</p>

<cc.complexity-theory><ds.algorithms><graph-algorithms><time-complexity><nondeterminism>
Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?
Michael Wehar
# Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?

(Asked by: username_0 on 2021-02-16)

The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices. A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ is adjacent to $c$, and $c$ is adjacent to $a$.

It is known that Triangle Finding is closely related to Boolean matrix multiplication and that Triangle Finding is deterministically solvable in $O(n^{\omega})$ time where $\omega$ is the matrix multiplication exponent. Also, it is known that $\omega < 2.373$.

**My Question:** Is the complement of Triangle Finding solvable more efficiently with nondeterminism? In particular, is Triangle Finding in $coNTIME(\tilde{O}(n^2))$? If this is not known, would there be any interesting implications if it was true?

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, time-complexity, nondeterminism


---

## 1 answers

### Answer by username_0 on 2021-02-16. Score: 7

**Update:** Sadly, it seems that my initial idea (see below) was incorrect, but it led to some fruitful discussion in the comments. As a result, the question is still open.

Please let me know if you have any ideas. :)

---

**Initial Idea:** One way to solve Triangle Finding is to find all pairs of vertices that are connected by a path of length 2. Then, you check if there is an edge between any of these pairs.

A standard way to compute all pairs of vertices that are connected by a path of length 2 is to square the adjacency matrix of the graph. We can perform Boolean matrix multiplication for the squaring. All of the 1's in the result will represent pairs of vertices that are connected by a path of length 2.

With nondeterminism, we can compute Boolean matrix multiplication of two n by n matrices in $\tilde{O}(n^2)$ time by guessing the witness for Boolean matrix multiplication (the concept of witness for Boolean matrix multiplication has been discussed in [1] <https://doi.org/10.1007/s00453-012-9742-3> and [2] <https://doi.org/10.1109/SFCS.1992.267748>). Finally, we check in $O(n^2)$ time if all of the pairs of vertices do not form edges. **<- This paragraph doesn't quite work.**

> **Comments:**
> **username_1**: Hi Michael, I don't see how the two references you cite solve the problem. Suppose you guess the output of matrix multiplication. For those output entries which are 1, yes you can guess witnesses. How do you prove the 0 entries are correct, nondeterministically, in approximately n^2 time? You have to prove there is *no* witness in the matrix squaring for all 1-entries in the adjacency matrix, this is what you would need to prove there is no triangle.  
> **username_0**: Thank you for your comment!  The references define the concept of witness for Boolean matrix multiplication.  I cited them only to provide background on this concept.  
> **username_0**: I think that you made a good point.  The witness for Boolean matrix multiplication may only help identify entries that should be 1's.  Let me think about this more.  
> **username_0**: Looking at this again, you would need a for all quantifier to check the 0's efficiently.  In other words, we can guess and check a witness for Boolean matrix multiplication with a $\Sigma_2 TIME(\tilde{O}(n^2))$ machine which might still be interesting.  But, as far as I can tell, we don't seem to get triangle finding in $coNTIME(\tilde{O}(n^2))$.  I will update my incomplete / flawed answer tomorrow.  
> **username_1**: I know there is a Merlin Arthur protocol for proving there are no triangles running in close to linear time (in the number of edges), but I don't know a nondeterministic algorithm. It is an interesting problem! In the literature the related problem of matrix multiplication verification has been studied. (If you could verify a matrix mult in n^2 time, even with nondeterminism, you would be done.) One can verify a matrix mult quickly with randomness, this is known as Freivalds's checker. But I don't know how to do it with nondeterminism.  

---

