Newest Questions
13,556 questions
1
vote
0
answers
17
views
Shannon entropy of a regular clock signal
The notion of Shannon entropy is usually applied to information sources which create symbols as a sequence of i.i.d. random variables. Entropy is also applied to individual sequences, e.g. in the ...
- 111
0
votes
0
answers
13
views
VLSI layout of a pyramid computer with bounded wire crossings and local routing
I am looking for a VLSI layout of a pyramid computer (a hierarchy of 2D meshes where each level has $1/4$ the processors of the level below, with each processor connected to its parent and four ...
5
votes
0
answers
39
views
Decidable fragments of first-order logic over finite structures
I've found a lot of classical references about decidable fragments of first-order logic (two-variable, guarded, bernays-schönfinkel-ramsey, Ackermann, etc.).
But which are the known decidable ...
- 2,072
3
votes
2
answers
96
views
Algorithms for recovering small s,e from As+e=b (mod q)
Let
$$
\mathbb Z_q=\mathbb Z/q\mathbb Z,
$$
where $q$ is prime. I consider the case where $B$ is fixed, $n$ grows, and
$$
q\approx 1024nB^2.
$$
Let
$$
A\in\mathbb Z_q^{n\times n}
$$
be a nonsingular ...
- 31
0
votes
0
answers
27
views
Structural typing where the 'primitives' are complex objects: is this a known concept?
I'm developing a framework in which structural relationships between objects are derived top-down through transformations between them, rather than built bottom-up from primitive types. I'd like to ...
- 101
2
votes
0
answers
91
views
Is injectivity of constructors for (large) inductive types in Prop, such as squashing, consistent?
I am defining a simple "squashing" type, which lives in impredicative Set, but we may as well consider that I'm using Prop, as the same issue appears (and I believe would be no different, ...
- 499
-1
votes
0
answers
35
views
Language with high polynomial lowerbound and simple description for single tape turing machines
There are quite a few language that are $\Omega(n^2)$ for single tape turing machines that are ease to explicitly write code for to check if a string belongs to the language, such as PALINDROME. Does ...
- 143
0
votes
1
answer
48
views
Advice strings vs relativization for equality of complexity classes (L/poly=SL/poly?)
Hi I know for an oracle O it is not the case perse that if two complexity classes A=B then A^O = B^O. I was wondering if this is also the case for advice strings. Is it the case for example if A=B ...
- 143
0
votes
1
answer
89
views
Does taking complements of complexity class inclusions imply NP = coNP? [closed]
It is established that (1) NP subset PSPACE and (2) coNP subset PSPACE and (*) for all sets A,B, A subset B iff coB subset coA.
Then can't we apply (*) to (1) and (2) to get that PSPACE subset coNP ...
user80441
2
votes
1
answer
75
views
On modular exponentiation and its parallelization
Let $a,g$ and $N$ be integers and we are required to compute $$g^a\bmod N.$$
WLOG if the order of the subgroup generated by $g$ is known then we can assume $0\leq a<N$. Assume we know the order of $...
- 41
0
votes
0
answers
137
views
Has this SAT solving idea been explored already?
For each variable x_i:
Set x_i = 0. If conflict occurs, collect all clauses involved in the conflict.
Set x_i = 1. If conflict occurs, collect all clauses involved in the conflict.
Take each clause ...
- 21
1
vote
1
answer
162
views
Does this proof show that $NC \subsetneq NP$?
Even though it's suspected that $NC \subsetneq NP$, as far as I know, it hasn't been proven. I think I've come up with a proof for it, but it seems too simple, so I'm thinking it must be wrong ...
- 453
-1
votes
0
answers
54
views
On Logspace $+$ reducibility for number of spanning trees for planar graphs
Given two $0/1$ matrices $M_1$ and $M_2$ we can construct two $SAT$ formulas $\varphi_1$ and $\varphi_2$ respectively whose number of solutions is exactly the permanent of $M_1$ and $M_2$ respectively....
- 13.8k
-1
votes
0
answers
52
views
Specification languages for functional programming
I'm trying to understand the code of the functional language Factor. Many functions defined by mutual recursion, untangling a tangle of snakes, looking for tails. How can I clearly write down what I ...
1
vote
1
answer
53
views
Number of propositional queries to check satisfiability of an LTL formula
An LTL formula $f$ is satisfiable if there is a trace $t$ of subsets of a set of atomic propositions AP that satisfies the semantic implication relation $t \models f$.
Given a formula $f$, is anything ...
- 1,113