All Questions
12,402
questions
0
votes
0
answers
11
views
What is the relation between these two complexity classes -$FL_{log}(RLP)$ and $FL_{||}(RLP)$?
Let $FL_{log}(NL)$ be the functional logspace class which makes logarithmically many adaptive queries to $NL$.
Let $FL_{||}(NL)$ be
the functional logspace class which makes polynomially many parallel ...
- 12.6k
-1
votes
1
answer
72
views
What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?
There is an ever going trend to believe that a large number of NP-Complete or NP-Hard problems can be solved using quantum heuristics.
I have observed, a common trend, to take any sort of ...
- 141
1
vote
0
answers
12
views
Is minimum knot crossing number elementary recursive?
One result in knot theory is that link crossing number is NP-hard. Another result is that the equivalence problem for knots and links is elementary recursive. So, given that the equivalence problem is ...
0
votes
0
answers
38
views
How to formulate the log-rank conjecture for non-boolean functions?
The log-rank conjecture states that there is a constant $C$ such that for every two-party Boolean function $f$ it holds: $D(f) = O((\log \text{rank} (f))^C)$.
If $f$ is not a boolean function then ...
- 1,881
0
votes
0
answers
13
views
What is an efficient algorithm to check for equivalence on symmetric interaction combinators?
Symmetric interaction combinators are a graph-rewriting model of deterministic computation derived from Lafont's interaction nets. In the paper "Observational Equivalence and Full Abstraction in ...
- 3,077
0
votes
0
answers
34
views
help me understand what semiprime factorizations are worth
Based on a response I received in another post, I would like to ask this question.
Are there semiprimes that are not very interesting in terms of research and are not worth factoring?
Are only the RSA ...
7
votes
1
answer
525
views
Why the "balanced vs constant function" problem is not a proof that P ≠ BPP?
Recently, I came across the problem of figuring out whether a given binary function $f(x)$ is constant (0 for all values of $x$ or 1 for all values of $x$) or balanced (0 for half of values and 1 for ...
- 73
2
votes
1
answer
51
views
Fine-grained average-case derandomization
Many believe derandomization with polynomial overhead, $\mathsf{P} = \mathsf{BPP}$,
because it follows from $2^{\Omega(n)}$ circuit lower bounds for $\mathsf{E}$ (IW97).
Do we have any evidence for or ...
2
votes
0
answers
26
views
What are some practical applications of inductive-inductive types?
By "practical applications" I mean in usual programming/industry. I am particularly interested in cases where the inductive-inductive types cannot be easily replaced by inductive-recursive ...
- 121
-1
votes
0
answers
62
views
How can one implement universal turing machines on general languages?
In most resources, I found that the statement of universal Turing machines assumes that the input alphabet for all Turing machines $T$ is given to be identical (e.g. $\{0,1\}$) as this gives enough ...
- 167
3
votes
1
answer
121
views
Is there an efficient algorithm to check for duplicator-invariant equivalence on symmetric interaction combinators?
Consider the 3 symmetric interaction combinator nets below:
Despite being different nets, they are equal, in the sense that, if we view white nodes as lambdas and applications, and black nodes as ...
- 3,077
0
votes
0
answers
49
views
Bin Covering problem with variable bin sizes
I have a decision problem that I cannot seem to map to a standard studied problem, although it seems similar to a few. I am wondering if anyone has come across this problem before, or if someone can ...
2
votes
0
answers
35
views
Linear-time maze exploration for finite automaton with pebbles?
Blum and Kozel have shown that a robot with the computational capabilities of a finite automaton can visit all $n$ cells in a quadratic maze when the robot is equipped with two pebbles which it may ...
- 21
6
votes
1
answer
102
views
Is DFA language inclusion decidable in quasi-linear time?
Given two DFAs $A_1$ and $A_2$, we want to decide whether $\mathcal{L}(A_1) \subseteq \mathcal{L}(A_2)$. Of course, one can compute whether $\mathcal{L}(A_1) \cap \mathcal{L}(A_2) = \mathcal{L}(A_1)$. ...
- 93
2
votes
1
answer
90
views
Complexity of polygon intersection test
In the book "Spatial Databases: With Application to GIS (The Morgan Kaufmann Series in Data Management Systems)", there's a section on simple polygon intersection detection , and it mentions
...
- 123
1
vote
0
answers
19
views
Given several $a_i$-$r$ paths in a planar graph how ``balanced" of a tree rooted at $r$ can I make?
Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and several $a_i$-$r$ paths $P_i$ in a planar graph $G$.
I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ that minimizes the ...
- 237
2
votes
0
answers
46
views
Is there a term for expander-like graphs that expand only large subsets?
I would like to find a bipartite graph $G(L, R)$ with the following properties/constraints:
For every subset $S \subseteq R$ with $\bf{|S| \geq \alpha |R|}$, its neighborhood $\Gamma(S)$ satisfies $|\...
- 21
3
votes
1
answer
70
views
Priority queue implementation with both find-min and delete-min $o(\log n)$
Question: There are several priority queue implementations listed on Wikipedia, along with amortized complexities of each of their basic operations: Does anyone know of an implementation in which the ...
12
votes
4
answers
1k
views
Where is the model theory in programming language theory?
I have a background in mathematical logic and am trying to learn some programming language theory. In the syntax of, say, first-order logic, one of the first distinctions you learn about is between ...
- 693
-7
votes
0
answers
43
views
Prove your Computational Theory Skills, Bounty Test. Could you resolve this issues? [closed]
Prove directly that the functions defined below are recursive primitives by defining them
from the initial or reorganization functions using the operations of composition, combination and
...
3
votes
0
answers
44
views
Property testing algorithm for isomorphism to a balanced 3-sided complete graph
I am looking for testing algorithm in the dense graph model, that checks for a graph with $3n$ vertices whether it's isomorphic to a balanced 3-sided complete graph with $n$ vertices in each set. The ...
- 31
4
votes
0
answers
83
views
Arithmetic Circuit Hierarchy?
The answers to the following question -
Hierarchy theorem for circuit size
give a "circuit hierarchy theorem" for boolean circuits. Does there exist a similar hierarchy theorem for ...
- 141
0
votes
0
answers
45
views
Explanation of Complexity class $S_2^P$ with an example and its relation to polynomial hierarchy?
I am trying to understand the complexity class $S_2^P$ defined as (https://en.wikipedia.org/wiki/S2P_(complexity)) $S_2^P$ is a complexity class, intermediate between the first and second levels of ...
- 314
1
vote
0
answers
39
views
Oracle for the permanent-of-gaussians problem
In this paper, Aaronson and Arkhipov formulate the $GPE_\times$ problem as follows: given an $n \times n$ matrix $X$ of i.i.d. Gaussian random numbers, find the permanent of $X$ up to multiplicative ...
- 111
1
vote
0
answers
37
views
Asking boolean question on the nodes of a DAG to find the target node
We are given a DAG $G=(V, E)$ and an unknown target node $x \in V$ to find. There is a mechanism to probe a node, $y \in V$, to ask question of the form "Given the node $y$, is the target node $x$...
- 11
3
votes
0
answers
87
views
Cover all triangles of a graph with n subgraphs as small as possible
What is the smallest number $s(n,\Delta)$ such that for any undirected simple graph $G=(V,E)$ with $n$ vertices and $\Delta$ triangles, there exist $n$ subgraphs of $G$ covering all triangles where ...
- 63
0
votes
0
answers
60
views
Can every reducible multivariate polynomial be partitioned into product of univariate polynomials of algebraically independent elements?
Lets say we define a reducible multivariate $f \in \mathbb{F}[x_1,...,x_n]$ to be partionable by $y_1,...,y_r \in \mathbb{F}[x_1,...,x_n]$ iff
\begin{equation}
f(x_1,,,,.x_n) = f_1(y_1)\cdot f_2(y_2) \...
1
vote
0
answers
43
views
Why the $K_{d,d}$-free set cover problem is easier?
In parameterized complexity, $k$-set cover is W[2]-hard. The definition of $k$-set cover is as follows:
Input: A ground set $U$ and a family of sets $\cal{F}$;
Parameter: $k$;
Output: Whether there ...
- 19
6
votes
0
answers
156
views
Baker–Gill–Solovay Theorem: why $2^n/10$ steps?
Context
I'm teaching an introductory complexity theory course right now and although I work in adjacent areas, I'm not an expert on complexity theory myself, so I'm still in the process of working ...
- 263
0
votes
0
answers
27
views
Do we need generic libraries of the SQL language?
Sorry I don't know where to post this question as it's interdisciplinary of progLang, softEng and databases.
When I program in SQL I frequently need to write duplicate code of similar functionalities. ...
-4
votes
1
answer
53
views
Does a rock falling down a hill perform computation?
Imagine a rock in the shape of a chessboard with pieces in a certain configuration.
Throw the rock down a particular hill. The hill is shaped in such a way that, given the correct throw, the ...
1
vote
1
answer
64
views
Can I define nested mutually dependent types in Coq?
I am trying to model the following in Coq, which works fine in Haskell (below is Haskell code):
...
- 13
-2
votes
0
answers
84
views
What evidence is there for $\oplus P\not\subseteq\oplus NC^1$ if $PH\subseteq BPP$?
If $\oplus P\subseteq\oplus NC^1$ then by $PH\subseteq BPP^{\oplus P}$ we have $PH\subseteq BPP$.
Assume $PH\subseteq BPP$. Then what further evidence we have against $\oplus P\subseteq\oplus NC^1$? ...
- 12.6k
0
votes
1
answer
77
views
Formal differences between emulation and simulation?
Recently this question came up, and I've been unable to find a concrete answer.
When I was reading this paper on CRDTs, I was a little perplexed by the notion of emulation here in theorems 3.1 and 3.2....
- 11
3
votes
0
answers
85
views
Influence for boolean functions on larger domains
Most of the literature on boolean function complexity considers boolean functions on $\{0,1\}^n$, but I am not finding very much about functions over larger (finite) domains. Specifically, fix a ...
- 1,242
3
votes
1
answer
201
views
Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable
It is known that the problem of integer linear programming is NP-hard, but its fractional relaxation can be solved in polynomial time. The concept of fractional relaxation can be applied to any ...
- 1,922
4
votes
1
answer
158
views
Concrete version of KKL Theorem
The Kahn–Kalai–Linial (KKL) Theorem says that for any balanced Boolean function $f:\{−1,1\}^n→\{−1,1\}$ we have $\max_i {\bf Inf}_i(f) = \Omega\left(\frac{\log n}{n}\right)$. I am looking for a ...
- 1,242
1
vote
0
answers
65
views
Perm and Det mod $2^k$ - II
Given a $0/1$ square matrix, the permanent and determinant modulo $2^k$ is in $\oplus P$ and $\oplus L$ respectively for any fixed $k$. In fact both are in $\oplus L$ (in fact in $\oplus SPACE(k^2\log ...
- 12.6k
1
vote
1
answer
178
views
Type of the Recursor in Lean
I need some help working through the type of the recursor, the eliminator for the inductive type. If
$F=\forall a::\alpha.\mathsf{U}_\ell$
$P=\mu t:F.K$
$K=\sum_c(c:\forall b::\beta.tp[b])$
$u::\...
- 13
0
votes
0
answers
51
views
Input-Output Machines
From what I know, there is a vast literature on language recognizers in computer science.
Language recognizers are machines (e.g., Finite State Automata, Pushdown Automata, Turing Machines, ...) that, ...
- 101
1
vote
0
answers
40
views
Max Flow Routing
Let G = (V,E,S,I,T) be a directed flow network with nodes V, edges E with unit capacity, source nodes S $\subseteq$ V, intermediate nodes I $\subseteq$ V, and target nodes T $\subseteq$ V. The problem ...
- 11
2
votes
1
answer
95
views
Perm and Det mod $2^k$ - I
Given a $0/1$ square matrix, the permanent and determinant modulo $2^k$ is in $\oplus P$ and $\oplus L$ respectively for any fixed $k$. In fact both are in $\oplus L$ (in fact in $\oplus SPACE(k^2\log ...
- 12.6k
5
votes
0
answers
50
views
W[t]-containment of partial covering problems
I would like to know more about the W[t]-containment of partial covering problems. Especially, I am interested in the question whether Partial Set Cover (Problem Definition at the end of the question) ...
- 81
0
votes
0
answers
21
views
Can we ensemble multiple models using the same algorithm but with different features?
I am a beginner in machine learning and I wonder if I have any misinterpret or misunderstanding of the ensemble learning concept itself.
As far as I know, the more diverse or unrelated the model, the ...
- 1
1
vote
1
answer
38
views
Efficient algorithm/ implementation to compute Transitive Closure of a Rule with respect to a Relationship
(Recalling some) Definitions:
Fix a finite collection of finite sets: $A_1,\ldots,A_k$. Then relationship $R\subseteq A_1 \times A_2 \times \ldots\times A_k$. (Remark: $A_i$'s need not be distinct.)
...
- 111
2
votes
0
answers
75
views
Variants of complexity classes that allow "adversarial inputs"?
Wikipedia defines BPP as follows:
Alternatively, BPP can be defined using only deterministic Turing machines. A language L is in BPP if and only if there exists a polynomial p and deterministic ...
- 271
0
votes
0
answers
83
views
When Exponential Costs are Essential for NP-Hardness?
In many NP-hard problem there is a budget constraint. Each element $e$ in the instance has a certain cost $c(e)$ and a profit $p(e)$; a feasible solution $S$ for the considered problem cannot exceed ...
- 103
3
votes
0
answers
205
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
- 20.8k
-4
votes
1
answer
145
views
factoring large numbers
I didn't get a reply to my previous post maybe because my question was too stupid?
I'm asking this forum for help in understanding how far we are from factoring very large semiprimes
I'll try to ...
0
votes
0
answers
33
views
Is SZK dependent on the verifier’s model of computation?
What if instead of a probabilistic TM, the verifier in the definition of SZK was a quantum TM?
How would this affect its relation to other classes? Would Statistical Difference still be a complete ...