All Questions

Filter by
Sorted by
Tagged with
-1
votes
0answers
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
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 ?
-2
votes
0answers
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 ...
0
votes
0answers
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 ...
5
votes
0answers
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, ...
1
vote
0answers
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 ...
-3
votes
1answer
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. ...
1
vote
1answer
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 ...
-1
votes
0answers
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$$ ...
1
vote
1answer
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 ...
5
votes
1answer
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 ...
1
vote
0answers
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 ...
5
votes
0answers
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 ...
0
votes
0answers
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 ,...
6
votes
0answers
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 ...
-4
votes
1answer
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 ...
1
vote
0answers
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
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. ...
3
votes
1answer
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, ...
0
votes
1answer
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 ...
0
votes
0answers
62 views

Is the knapsack variant with small profit and unlimited repetition of items NP-hard?

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 $\...
1
vote
0answers
25 views

Minimum graph cycle basis respect to non-empty pairwise intersection of cycles

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 = \{...
21
votes
3answers
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, ...
18
votes
14answers
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 ...
-4
votes
0answers
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 ...
-4
votes
0answers
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&...
-3
votes
0answers
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 ...
-7
votes
0answers
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.
11
votes
1answer
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?
1
vote
0answers
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 ...
2
votes
0answers
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 ...
-3
votes
0answers
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 ...
5
votes
0answers
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
3
votes
1answer
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 ...
-1
votes
1answer
31 views

Applying hypothesis with unknown variables [closed]

0 I'm trying to prove the following lemma about functions on natural numbers ...
5
votes
2answers
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.
0
votes
0answers
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 ...
1
vote
0answers
51 views

Reference request on using Kolmogorov complexity to measure the simplicity of models

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 ...
0
votes
0answers
59 views

RSA as an Hidden Subgroup Problem

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 $\...
6
votes
1answer
138 views

Existing implementation of Scott's reduction?

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 ...
2
votes
0answers
85 views

What's the constant coefficient of the Coppersmith-Winograd algorithm?

Every source I can find just says "too big to be practical."
-2
votes
0answers
62 views

Describing circuits with bits

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 ...
2
votes
0answers
29 views

Reducing Parameterized Problems (whose solution size can be “large”) to W[i]-complete problems (for fixed i)

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 ...
-1
votes
0answers
78 views

CNF to exponentially larger HORN [closed]

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 ...
3
votes
0answers
105 views

Bounds on this Strategy for Separating Words

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 ...
3
votes
2answers
147 views

Match a string agains a set of regexes

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 ...
3
votes
0answers
82 views

Origin of simulation relations for compiler correctness

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 ...
6
votes
2answers
243 views

find the most similar topological ordering of a dag

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

15 30 50 per page
1
2 3 4 5
217