# All Questions

10,807 questions
Filter by
Sorted by
Tagged with
18 views

### If machine learning can cover any CS problem, wouldn't it prove that P=NP?

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 ...
10 views

### Does an answer-set in answer-set-programming have to be a model of the program

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 ...
20 views

### Existing implementation of “grounding for first order logic formulas”?

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 ?
20 views

### How to approach SAT-related reduction/proofs? (Double-SAT)

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 ...
12 views

### High probability bound on the difference between expected cumulative reward and cumulative reward

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 ...
40 views

### reference request: greedy algorithm for fractional interval covering

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, ...
33 views

### On solving Planar Circuit SAT

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 ...
39 views

### tables of reductions in literature

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. ...
67 views

### Formal theory about explaining algorithms

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 ...
20 views

### System of equations with infinite dimensional variable

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$$ ...
79 views

### Is Scott's reduction sound for $\mathrm{FO}^2$ with equality?

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 ...
80 views

### Does focused proof search ever have to backtrack across the choice of focus formula?

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 ...
120 views

### Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?

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 ...
83 views
+50

### Complexity of finding the most likely edge

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 ...
8 views

### No 13 in the sequence [migrated]

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 ,...
71 views

### Counting on grid graphs

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 ...
41 views

### Problems people face with computer science professions (outside of work)

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 ...
23 views

### granularity of bidirectional breadth-first search

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 ...
50 views

### 3SAT ≤L SUBSET-SUM

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 ...
26 views

### What is the best way to find circles that contain a given point (in 2D)?

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. ...
160 views

### How can I find the PhD thesis of C.A. Ellis?

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, ...
42 views

### Sample graph dataset for testing algorithms

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 ...
62 views

4k views

### Implications of proving NP=RP on complexity theory

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, ...
2k views

### Examples of collapsing hierarchies

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 ...
32 views

### What to choose Deep learning or Artificial Intelligence after learning basic Machine Learning? [closed]

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 ...
21 views

### TPTP proof checker fails for theorems [closed]

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&...
62 views

### Relation between Randomized and Distribution complexity

$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 ...
59 views

### I believe I am able to prove that $NP\subseteq P$ any idea how I show that $P\subseteq NP$ [closed]

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.
254 views

### When was co-NP introduced for the first time?

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

### Who introduced the notion of Non-Deterministic Polynomial time?

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 ...
47 views

### The Edge Cover Equilibrium Problem

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 ...
66 views

### What are Recommender systems papers that everyone should read? [closed]

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 ...
77 views

### Category theory lambda cube?

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
95 views

### Normal forms for counting quantifiers?

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 ...
31 views

### Applying hypothesis with unknown variables [closed]

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

### Categorical equivalent of higher order logic

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.
22 views

### Optimal rule for multiple stopping times for defect finding [closed]

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 ...