Theoretical Computer Science Questions, Problems & Solutions : TransWikia.com ~ Page 3

Embedding a n-tree into a b-dimensional space

Given a (directed) n-tree $T=(N,E,r)$ rooted in $rin N$, I want to represent each node $nin N$ at most as a $m$-dimensional vector $v_nin mathbb{R}^m$...

Asked on 10/30/2021 by jackb

2 answer

PPAD and Quantum

Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class...

Asked on 10/30/2021

2 answer

3-colourability of Eulerian maximal planar graph

The following paragraph is from this answer by David Eppstein (emphasis mine).A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd...

Asked on 10/30/2021

2 answer

Is mathematical proof itself NP-hard?

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help...

Asked on 10/30/2021

1 answer

An efficient Beta-Equivalence algorithm?

Is there an efficient algorithm to determine if two terms are beta-equivalent? I'm specifically curious about simply-typed-lambda-calculus, so you can assume both terms are strongly normalizing. I know a simple...

Asked on 10/30/2021 by user1636815

1 answer

3SUM Complexity—A special(?) Case

In the paper “Consequences of Faster Alignment of Sequences” byAmir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here...

Asked on 10/30/2021 by kodlu

2 answer

Uniquely 4-colorable Planar Graph Conjecture?

My question is on Uniquely 4-colorable Planar Graph Conjecture mentioned inOn purely tree-colorable planar graphs (and other papers of same(?) team such as "Theory on Structure...

Asked on 10/30/2021

0 answer