All Questions

Filter by
Sorted by
Tagged with
1
vote
0answers
29 views

MaxCut instance with least number of cuts

Let us look at all 4-regular undirected graphs with $n$ nodes and edge weight equals to 1 for all edges. Out of these graphs, I would like to find the MaxCut instance with least number of cuts in its ...
3
votes
7answers
120 views

What are some algorithms where space complexity tends to be the limiting factor in practice?

Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? ...
1
vote
1answer
45 views

Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments

Suppose there is a reduction which, given a $\oplus \text{SAT}$ instance $\phi$, returns another $\oplus \text{SAT}$ instance $\psi$ having all the following properties: The size of $\psi$ is ...
-1
votes
0answers
42 views

How can I calculate nonstandard binary representations quickly?

I'm looking to convert standard unsigned binary numbers (machine integers) to each of several similar nonstandard binary representations. First representation Each digit is 1, 2, or 3. Second ...
3
votes
0answers
51 views

Best known hidden constant in complexity of AKS sorting networks

The famous AKS sorting network allows one to sort $N$ elements via a circuit composed out of comparator gates, where the circuit has size $\mathcal{O}(n \log n)$ and depth $\mathcal{O}(\log n)$. The ...
3
votes
1answer
97 views

Polynomial evaluation at all different points

I have a polynomial $f(x_1,\ldots,x_{50})$ of 50 variables over binary field $GF(2)$. I want to evaluate at all $2^{50}$ points and check how many of them are 0. Ofcourse we can evaluate at all ...
0
votes
0answers
27 views

Hardwiring the output in a quantum circuit

In this paper, while using a diagonalization argument in Section $5$, the authors write: Fix some enumeration over all $poly(n)$-size quantum verifiers $M_{1}, M_{2},...$ which we can do because the ...
0
votes
0answers
42 views

Is this a reader monad?

I'm unsure whether the following three equations constitute a valid instance of a reader/environment monad on the simply-typed lambda calculus, where $\alpha$ is any type (I subscript some terms with ...
-5
votes
0answers
48 views

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

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 ...
-2
votes
0answers
19 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
36 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 ?
-3
votes
0answers
31 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
14 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
46 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, ...
3
votes
0answers
70 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
59 views

tables of reductions in literature [closed]

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. ...
2
votes
1answer
121 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
22 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
89 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
95 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
163 views
+100

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
1answer
129 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
75 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
42 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
51 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
27 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
172 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
67 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
5k 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
33 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 ...
-3
votes
0answers
64 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 ...
11
votes
1answer
261 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?
2
votes
0answers
185 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 ...
6
votes
0answers
81 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
97 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
32 views

Applying hypothesis with unknown variables [closed]

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

15 30 50 per page
1
2 3 4 5
217