All Questions

My (naive) comprehension is that any CS problem, both P and NP, could be expressed as a set of data to expose to ML computation. It doesn't matter how much time the ML algorithm would take to learn ...

I have found several definitions for the answer-set of a program P that go like this: An interpretation M is an answer set of a ground program P iff it is a minimal model of Pm, where Pm is the ...

I am sorry if this is off-topic here. I am looking for a simple implementation of grounding a function free first order logic formula. Does anyone know of any existing implementation ?

I am preparing for my exam next month and was stuck when it came to SAT reductions/proofs. Could someone help me out in understanding this question? Double-SAT = {< ϕ > | ϕ is a Boolean formula ...

Consider a MDP $M$ with a finite state space $S$ and a finite action space $A$. When executing an action $a$ in state $s$, the learner receives a random reward $r$ drawn independently from some ...

Reference Request I've found a natural greedy algorithm for the problem below. My question is: what is already known about fast algorithms for this problem (faster than general linear programming, ...

This enquiry is three-sided. Side 1 - State of the art Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$? Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$ assuming ...

I'm interested in tables of which problems are reducible to which other problems. Particularly for graph problems, but any such tables/graphs would be neat, just so I know how to look for them. ...

There is a lot of algorithms written in formal languages, but I have never seen any formal system which target is to explain or give a rationale behind an algorithm. It seems that when constructing ...

I have a system of equations of the following $$z(n)=c+\delta\big[p_1z(n+1)+p_2z(n-1)+(1-p_1-p_2)z(n)\big]~~if~~n\geq 0$$ and $$z(n)=\delta\big[p_1z(n+1)+p_2z(n-1)+(1-p_1-p_2)z(n)\big]~~if~~n< 0$$ ...

As per this paper by Grädel, Kolaitis and Moshe Vardi, they discuss computational complexity of satisfiability problem in $\mathrm{FO^2}$, In order to do this they use Scott's reduction. Which is the ...

There are a lot of different "focused" sequent calculi for lots of different logics, but my understanding is that many or most of them have the following flavor. First one divides the ...

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the ...

Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes. Now consider the following random process. First sample a uniformly random ...

There are "n" number of box's each box we can place 0-9 numbers .. condition is that 13 is not occurred at any place in sequence.. I take n = 3; and so total possiblities is 101010 = 1000 ,...

Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in $\#P$ and remain hard for grid graphs? Since there seem to be ...

I am writing an article for a classroom project shedding light on the major issues that Computer Programmers face outside of work. I am not really looking for anything too in-depth concerning ...

I tried posting this on stack overflow and it got no takers, decided to cross post here: One thing that I've never seen discussed about bidirectional breadth-first-search (which I'll abbreviate as ...

There's the common polynomial reduction from 3SAT to SUBSET-SUM as described here, but what about a log-space reduction from 3SAT to SUBSET-SUM? I came across this question a few days ago but still ...

Given $n$ circles all with radius $r$ and one point on a 2D plane, what is the best algorithm to find all circles that contain the given point. The circles and the point can change their positions. ...

I've searched for this article all over the web but couldn't find it. can anyone help me? Ellis, C.A. 1969. Probabilistic languages and automata. Rept. no. 355. Dept. Comp. Sc. University of Illinois, ...

I hope I'm addressing the right community. For a project for my students, I need to find some weighted graphs (oriented or not) to benchmark their algorithms (shortest paths, flows...). There are a ...

Consider the unbounded knapsack problem where we are given $n$ items of integral weights $w_i$ and integral profits $p_i$ . Given a max weight $W$, the goal is to maximize $\sum_i x_ip_i$ subject to $\...

I'm trying to understand the following problem if anyone can help I'll be very grateful Instance: undirected, unweighted, connected graph graph $G=(V,E)$. Question: find a minimum cycle basis $B = \{...

Edit: As indicated below by Mahdi Cheraghchi and in the comments, the paper has been withdrawn. Thanks for the multiple excellent answers on the implications of this claim. I, and hopefully others, ...

Are there interesting examples of "collapsing hierarchies" in computer science? The formal definition of a hierarchy here would be a class of languages/problems/objects which is ...

I Learned basics from Machine Learning and its algorithm and I wanted to choose the on subject from deep learning and artificial neural network so I am confused which one to choose can any one guide ...

on TPTP, whenever I try to verify the proof of a theorem (for example SYN054+1) with the proof checker (GDV), it fails: http://www.tptp.org/cgi-bin/SystemOnTSTP?TPTPProblem=SYN054%2B1&...

$DistNP$ is contained in $AvgP$ does not imply that $NP=RP$ by https://dl.acm.org/doi/10.1109/CCC.2011.34. Do we know if $NP=RP$ then $DistNP$ is contained in $AvgP$? or $PP=BPP$ then $DistNP$ is ...

I believe I am able to prove that $NP\subseteq P$ any idea how I show that $P\subseteq NP$? I believe it will revolutionize our modern perception about computability.

My best finding is Pratt's 1975 article. Is there any earlier mention of co-NP?

In his 1972 paper, Richard Karp provides a definition of NP (section 3, definition 4, p.91). It this the original definition of the class NP or is there a previous one? Edit Edmonds mentions the idea ...

Let the Edge Cover Equilibrium Problem be the following: INPUT: a simple undirected graph $G$. OUTPUT: YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...

What are the Recommender systems papers that everyone should read? This question is inspired by a series of others (1, 2, 3) which proved to be extremely useful for me in the past; but focused on ...

If simply typed lambda calculus corresponds to cartesian closed categories, what types of categories do other calculi in the lambda cube correspond to? https://en.m.wikipedia.org/wiki/Lambda_cube

In the paper by [Erich Grädel and Martin Otto], the authors state that any formula in First Order Logic with two variables with counting quantifiers can be reduced to a formula of the form $$ \forall ...

0 I'm trying to prove the following lemma about functions on natural numbers ...

From Simply typed lambda calculus and higher order logic, I get the impression that HOL is STLC + equality + equality axioms. I was wondering if there is a particular kind of category modelling this.

Suppose a quality inspector is inspecting $b$ black amongst which $d_b$ are known to be defective and $w$ white gadgets amongst which $d_w$ are known to be defective. The gadgets come down along an ...

Have there been any serious attempts to use the notion of Kolmogorov complexity to measure the simplicity of models outside of theoretical CS? I mean models in the english sense - any logical set of ...

the Hidden Subset Problem (HSP) covers several known problems (e.g. Integer Factorization Problem, Discrete Logarithm Problem) as a special case: Definition [Hidden Subgroup Problem (HSP)] Let $\...

As per this paper by Grädel, Kolaitis and Moshe Vardi, they discuss computational complexity of satisfiability problem in $\mathrm{FO^2}$, In order to do this they use Scott's reduction. Which is the ...

Every source I can find just says "too big to be practical."

I'm currently reading the book Computational complexity from Arora and Barak. In chapter 6 (page 114) about Boolean functions the authors are proving the Karp-Lipton theorem, in the proof they use the ...

Note: Originally, this question was asked via a comment in this question, but was asked to post a separate question. :) I'm looking for any known reductions of the following: Given a parameterized ...

It is known that CNF-SAT is NP-Complete while HORN-SAT is P-Complete. Therefore we shouldn't expect a translation from CNF-SAT into HORN-SAT which results in a merely polynomially larger formula. That ...

Question Given binary string $z \in \{0,1\}^n$, let $f(z)$ be the smallest integer $k$ such that there exists a DFA with $k$ states, such that reading $z$ from a specific starting state, we end at a ...

There are several algorithms to match a (simple) string against a regular expression (see here). But if we have a lot of regexes, can we find one of them that matches the given string faster than ...

Leroy uses simulation relations as a means of showing compiler correctness; the basic idea is that a simulation relation is an asymmetric binary relation between states in two different small step ...

Given a permutation $L$ of the $n$ vertices of the directed acyclic graph $G=(V,E)$. Question: is it NP-hard to find the topological order of the $G$ that is the most similar to the given permutation $...