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

Number of connected components of a random nearest neighbor graph?

Let us sample some big number N points randomly uniformly on $[0,1]^d$.Consider 1-nearest neighbor graph based on such data cloud. (Let us look on it...

Asked on 10/30/2021 by Alexander Chervov

3 answer

In the neutral zone between polynomial and sub-exponential

What are examples of problems that are known to be sub-exponential, butare known to be non-polynomial, orare not known to be polynomial?EDIT. Here is what I mean by sub-exponential (apologies...

Asked on 10/30/2021 by Dominic van der Zypen

7 answer

Can modern SAT-Solvers utilise the symmetry of First Order Logic?

Apologies if the question is trivial or is wrongly stated, I am a Physicist! Assuming that we have a universally quantified first-order logic sentence, all variables are universally quantified, defined...

Asked on 10/30/2021 by SagarM

3 answer

Understanding definition of #P

Valiant defined $#P$ in terms of a counting TM, which is a NTM that outputs the number of solutions [1]. I am a bit stuck with the following two...

Asked on 10/30/2021

2 answer

What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?

Unlike hierarchy collapse arguments for classical complexity we have that quantum complexity is different.What evidences are there that $PP$ is in $BQP$?What evidences are there that $PP$...

Asked on 10/30/2021

1 answer

Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice...

Asked on 10/30/2021

2 answer

Does this notation have a special meaning?

I am currently reading a paper and I don't know how to interpret this notation you can see on the screenshot. http://moxn.brainex.de/pub/dfg.png...

Asked on 10/30/2021 by moxn

2 answer

What's new in purely functional data structures since Okasaki?

Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few:IntMap (also invented...

Asked on 10/30/2021

6 answer

Fully dynamic algorithms for strong components of a directed graph

I'm faced with the problem of maintaining the strong components of a directed graph under insertions/deletions of edges and vertices. As noted in one of the answers to a closely-related...

Asked on 10/30/2021 by factotum

1 answer

Optimization Problem on a Directed Graph

I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of...

Asked on 10/30/2021 by GraphMan

2 answer

Page 2 of 5
1
2
3
4
5

Ask a Question

Get help from others!

Theoretical Computer Science : Recent Questions and Answers (Page 2)

Ask a Question