1. All Categories
  2. Theoretical Computer Science

Theoretical Computer Science : Recent Questions and Answers

Find answers to your questions about Theoretical Computer Science or help others by answering their Theoretical Computer Science questions.

Complexity of Model Enumeration in function free, equality free, First Order Logic with only Unary Predicates?

This question has inspired the following two questions.Given a first order logic language, with only unary predicates, finite number of variables, $forall$ and $exists$ i.e no...

Asked on 11/28/2021

2 answer

Reducing the Height of Context-Free Grammars

Let $G$ be a context free grammar in Chomsky normal form (CNF) with language $L(G)subseteq Sigma^n$. In other words, all strings generate by $G$ have size $n$. Say that...

Asked on 11/26/2021 by Mateus de Oliveira Oliveira

2 answer

Dynamic matrix-matrix multiplication

Suppose A and B are initial Boolean matrices. Let C = A*B. Suppose one can perform the sequence of the next operations: "set A[i,j] = 1", "set B[i,j] = 1"....

Asked on 11/26/2021 by gsv

0 answer

Comparing two graphs when starting from a single edge

Let's assume that we are given two graphs $G_1$ and $G_2$ defined by the two following nicely drawn pictures. Black numbers label the nodes, red numbers show the...

Asked on 11/23/2021 by Freiburger0

0 answer

Proving membership in W-hierarchy when problem is not parameterized by its solution size

I'm curious about the following general problem: Suppose that we have a parameterized problem whose input is $x$ and parameter is $k$ (which is NOT the size of...

Asked on 11/19/2021 by Haden Hooyeon Lee

1 answer

Find a boundary from set of 3d line segments

I have a set of n 3d line segments [(p1_start,p1_end), (p2_start,p2_end),....(pn_start,pn_end)].(I believe that they shod be nin-intersecting...)These segments represent a (closed) boundary. I am looking for...

Asked on 11/14/2021

1 answer

approximate maximum clique given vertex cover

I have a non optimal vertex cover of size k of a graph G, and I want to get a (1+epsilon)-approximation kernel of size linear in k for maximum clique...

Asked on 11/06/2021 by markHall

1 answer

Any fundamental papers in TCS which were found to be incorrect/wrong later?

I am asking this question out of curiosity. I recently encountered this well-known paper on (published in 2009):the hardness_of_Euclidean_kmeans The paper showed that the previous NP-hardness result...

Asked on 10/30/2021

9 answer

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

Ask a Question

Get help from others!

© 2021 All rights reserved.