## Top new questions this week:

### NP complete problem help

I'm currently trying to find a reduction to this problem: Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...

cc.complexity-theory np-hardness complexity-classes cg.comp-geom

### Context weakening as an explicit rule for languages of the the lambda cube?

I'm trying to formalize the syntax and typing judgments of the Calculus of Constructions in Coq. I'm choosing to use the Pure Type Systems presentation of CoC; however, I've seen mild variations in ...

type-theory calculus-of-constructions

### Why should we believe that $NEXP \not \subset P/poly$

I am sorry if this is not an advanced question. Most computer scientists believed that $Nexp \not \subset P/poly$ but they are not even close to this assumption. The main evidence that they are used ...

circuit-complexity derandomization nexp

### Tableau method for two-variable first-order logic

$FO^2$, i.e. two-variable first-order logic, has a NEXPTIME-complete satisfiability problem (see Grädel, Kolaitis and Vardi '97). However, the decidability and complexity of this fragment is proved by ...

first-order-logic
 answered by Bartosz Bednarczyk 1 vote

### Energy-Based Modeling vs Deep Learning

I am doing some research on machine learning algorithms in the context of a seminar, which focuses on Energy-Based Modeling vs Deep Learning specifically in working with images Modeling. Now I know ...

machine-learning

### Hardness of Approximation of Continuous Metric k-Median

First let me describe the metric $k$-median problem. Definition (Metric $k$-Median): Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ ...

approximation-algorithms approximation-hardness set-cover clustering
 asked by Inuyasha yagami 1 vote

### Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains

Let ${\cal L}=\{Y_1,..., Y_k, X\}$ be a finite relational language such that $X$ is a unary relation name. Let $\phi(X,\bar{Y})\in{\cal L}$ be a first-order formula (the formula can have the equality ...

cc.complexity-theory lo.logic terminology descriptive-complexity finite-model-theory
 asked by Erfan Khaniki 1 vote

## Greatest hits from previous weeks:

### Applications of Hamiltonian Cycle Problem

The Hamiltonian Cycle Problem and Travelling Salesman Problem are among famous NP-complete problems and has been studied extensively. I am looking for applications of the HamCycle and TSP. What are ...

graph-theory application-of-theory hamiltonian-paths

### What are the recent TCS books whose drafts are available online?

Following the post What Books Should Everyone Read, I noticed that there are recent books whose drafts are available online. For instance, the Approximation Algorithms entry of the above post cites ...

reference-request big-list books

### Major unsolved problems in theoretical computer science?

Wikipedia only lists two problems under "unsolved problems in computer science": P = NP? The existence of one-way functions What are other major problems that should be added to this list? Rules: ...

big-list open-problem

### Which is the limit of lossless compression data? (if there exists such a limit)

Lately I've been dealing with compression-related algorithms, and I was wondering which is the best compression ratio that can be achievable by lossless data compression. So far, the only source I ...

it.information-theory data-streams

### What is the contribution of lambda calculus to the field of theory of computation?

I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with functions/...

soft-question big-picture lambda-calculus ho.history-overview

### Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct? Also on topic: where else (on the internet) is its correctness being discussed? Note: the focus of this question text has ...

cc.complexity-theory np-hardness complexity-classes

### Problems Between P and NPC

Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...

cc.complexity-theory np-hardness big-list np-intermediate