All Questions

Filter by
Sorted by
Tagged with
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 ...
Turbo's user avatar
  • 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 ...
Marion's user avatar
  • 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 ...
Niklas Rosencrantz's user avatar
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 ...
Alexey Milovanov's user avatar
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 ...
MaiaVictor's user avatar
  • 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 ...
claudio G's user avatar
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 ...
Thiago's user avatar
  • 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 ...
Nicholas Brandt's user avatar
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 ...
Shiranai's user avatar
  • 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 ...
Thomas Tappeiner's user avatar
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 ...
MaiaVictor's user avatar
  • 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 ...
Rohan Bali's user avatar
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 ...
jfriemel's user avatar
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)$. ...
Janmar's user avatar
  • 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 ...
Lieven's user avatar
  • 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 ...
Hao S's user avatar
  • 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 $|\...
user2465561's user avatar
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 ...
Franklin Pezzuti Dyer's user avatar
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 ...
Siddharth's user avatar
  • 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 ...
Claudemizo_Brainer's user avatar
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 ...
Z.L's user avatar
  • 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 ...
ramseysdream111's user avatar
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 ...
J.Doe's user avatar
  • 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 ...
Alexey Uvarov's user avatar
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$...
Azam Ikram's user avatar
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 ...
walydna's user avatar
  • 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) \...
Rishabh Kothary's user avatar
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 ...
Hanchun Yuan's user avatar
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 ...
Manuel Eberl's user avatar
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. ...
Ligon Liu's user avatar
-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 ...
MeltyButter's user avatar
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): ...
Henri_S's user avatar
  • 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$? ...
Turbo's user avatar
  • 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....
NathanLiitt's user avatar
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 ...
user6584's user avatar
  • 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 ...
Erel Segal-Halevi's user avatar
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 ...
user6584's user avatar
  • 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 ...
Turbo's user avatar
  • 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::\...
Alex Byard's user avatar
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, ...
Sam's user avatar
  • 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 ...
sripurva's user avatar
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 ...
Turbo's user avatar
  • 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) ...
xtyner's user avatar
  • 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 ...
raven's user avatar
  • 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.) ...
Inspired_Blue's user avatar
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 ...
Jason Gross's user avatar
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 ...
John's user avatar
  • 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 ...
Mohammad Al-Turkistany's user avatar
-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 ...
user68942's user avatar
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 ...
Irna Mosa's user avatar

15 30 50 per page
1
2 3 4 5
249