# Tagged Questions

**5**

votes

**3**answers

538 views

### Are paths in HoTT perhaps just “cost-free” paths?

Homotopy type theory (HoTT) doesn't seem to say anything about "mutations" of values in type $T$, an important concept in computer science. Mutations occur when you "change a value" of some variable ...

**23**

votes

**5**answers

1k views

### Securing privacy of “who communicates with whom” under Orwell-like conditions

Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...

**3**

votes

**1**answer

124 views

### Subsets of $\omega$-regular lanuages accepted by automata with special acceptance condition

Let $\mathcal A = (X, Q, \delta, q_0, F)$ be a deterministic finite automata with the following acceptance condition on infinite words:
The automata accepts $\xi \in X^{\omega}$ with respect to $F$ ...

**9**

votes

**1**answer

409 views

### Categorical Semantics for Second-Order Logics

I am currently doing some work using a categorical semantics of first-order logic. The specific semantics I am using is due to Andrew Pitts, as described in:
Categorical Logic, Andrew M. Pitts, ...

**6**

votes

**6**answers

340 views

### Physical Disturbances to Computations [closed]

In this paper, page 7 (160 of the Journal), Fig 3, there is a particularly amusing (not to the authors!) caption:
"... On April 1 of year 2 in the $S_0$ experiment, the computer was hit by a cosmic ...

**0**

votes

**1**answer

629 views

### Proof of the lower bounds of time of algorithm working [closed]

I have asked this question on math.stackexchange already: http://math.stackexchange.com/questions/515920/lower-bounds-on-the-running-time
There are some problems, when there is non-trivial lower ...

**5**

votes

**2**answers

424 views

### A simple language and systematic computations

The following somewhat popular simple computer language was enjoyed on sci.math, sci.math.research, pl.sci.matematyka, and perhaps before and after at several places (I wish I knew it's exact ...

**2**

votes

**0**answers

86 views

### Is there any track for proving $D=NP$, besides showing that $D$ has polynomial-bounded universal quantifiers?

Background
By the MRDP theorem, every for every recursively enumerable set $S$, there exists a Diophantine polynomial $p$ such that
$$x \in S \iff \exists y_1, \dots, y_n \in \mathbb{N} \text{ such ...

**1**

vote

**0**answers

93 views

### Indecomposability of image transformations (pure algebra). Open questions

W-transformations -- definitions
We will consider a class called finite window transformations $\ T:C^\mathbb Z\rightarrow C^\mathbb Z\ $ defined a paragraph below; $\ \mathbb Z\ $ is the ring of ...

**18**

votes

**4**answers

900 views

### Kolmogorov complexity is the strongest noncomputable function

Yury I. Manin says that Kolmogorov complexity (in some nontrivial sense) is the strongest noncomputable function ("Колмогоровская сложность... невычислима... она во многих интересных смыслах ...

**5**

votes

**1**answer

425 views

### The relationship between P vs NP problem and “Kolmogorov complexity with time”

Let $P$ - polynomial($P(x) \ge x$), $n \in \mathbb{N}$, $l < log(n)$.
Problem1: "Is there program with length $\le l$ that print $n$ by using $\le P(log(n))$ time?"
Is it Problem1 $\in ...

**1**

vote

**0**answers

115 views

### Testing functional equivalence

We are looking for the most efficient (most recent, or best) techniques to check if two algebraic expressions (elementary, Calculus-type functions) are equivalent (or if an expression is equivalent to ...

**11**

votes

**2**answers

775 views

### Efficiently determine if convex hull contains the unit ball

Given a set of $n$ points in $\mathbb{R}^d$, is there an algorithm to determine if the convex hull contains the unit ball centered at the origin in polynomial time? The convex hull itself might have ...

**7**

votes

**1**answer

293 views

### Main problems on lattice-basis reduction algorithms (such as LLL)?

What are the main open problems on lattice-basis reduction algorithms (such as LLL)? I am looking for problems satisfying the following two conditions:
(a) their solution would likely be of some ...

**10**

votes

**2**answers

506 views

### What Turing-Complete models of computation carry a notion of time complexity that “agrees” with that of Turing Machines?

Certain models of computation are technically Turing-Complete, but cannot feasibly simulate a Turing Machine within the usual time constraints we hope for. One example of this is Godel's recursive ...

**1**

vote

**3**answers

189 views

### unbounded complexity

If a language L is decidable, does that imply that the is a computable function f such that L is in O(f(n)) ?
For example what would be the complexity class of the language of "provably halting ...

**9**

votes

**2**answers

388 views

### Where should I learn about Kolmogorov complexity of overlapping substrings?

I would like to know more about the relationship between the Kolmogorov complexity of a string and that of its substrings. The relation that up to an additive constant, $K(x,y) = K(x) + K(y\ |\ x, ...

**3**

votes

**1**answer

193 views

### Is there an easy decision algorithm for the inhabitation problem for simple types?

Consider the basic system of simple types usually known as $TA_\lambda$. One can prove that (as a consequence of the Subject Reduction Property and the fact that any typable term is strongly ...

**4**

votes

**0**answers

178 views

### Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...

**4**

votes

**0**answers

125 views

### Question about constructing an admissible ideal of a quiver of an algebra with the aid of a computer

Let $k$ be an algebraically closed field and $A$ a finite-dimensional, basic, connected $k$-algebra. Then $A$ is Morita-equivalent to a quotient of a path algebra $kQ/I$ and $I$ is an admissible ...

**7**

votes

**1**answer

357 views

### Constructing Metrics for specific Topological Spaces, and Refinements of the Cantor-Space in particular

I have a Problem in general, given some some Topological Space $(X, \tau)$ from which I know it is metrisable, how can I find a metric (that is at best in some sence constructive and easy, at the very ...

**2**

votes

**1**answer

312 views

### Problem to a solution

Consider an NP hard problem $\frak P$ which takes an input of length n
$\frak P$ can be solved partially by a factor $ p_i = p(n,i)\in$ [0,1)... by a polynomial time algorithm $\mathcal A(i)$ ...

**16**

votes

**5**answers

615 views

### Mathematics of privacy?

I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics?
Can we ...

**14**

votes

**2**answers

2k views

### Switching from pure mathematics (e.g. geometry) to more applied areas (e.g imaging) after Ph.D., as postdoc and chance of getting such a postdoc?

Before I start my question, I should probably mention that this question might not be the right question to ask here, but I tried academiabeta, and stackoverflow, but without getting any to-the-point ...

**0**

votes

**1**answer

149 views

### Interaction-based approximation for HP-complete λ-theory?

We are looking for a proof or counter-examples for the following hypothesis.
Two combinators $M$ and $N$ are solvable and equivalent in the HP-complete sensible $\lambda$-theory iff either
$$
\exists ...

**4**

votes

**3**answers

493 views

### What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity?

Let me begin with an example.
Consider the computable function $f(x) = 2x$. A Turing machine can implement this function in $O(|n|)$ steps: simply walk to the end of the input string, write a $0$, ...

**15**

votes

**3**answers

898 views

### How do we express measurable spaces using type theory?

A measurable space $(X,\mathcal X)$ consists of a set $X$ equipped with a $\sigma$-algebra of subsets $\mathcal X$. I would like to write computer programs involving measurable spaces, but to the best ...

**0**

votes

**0**answers

404 views

### Extended definition of unambiguous language and the existence of unambiguous grammar

Let's extend the unambiguity of language and grammar as follows:
a language $L$ is unambiguous if there is a grammar that generates every word in $L$ in a unique way, the grammar may be of type 0 or ...

**3**

votes

**0**answers

65 views

### Is the $d$-dimensional Arrangement of Trees still $NP$-hard?

The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...

**3**

votes

**1**answer

183 views

### Question about the elementary divisors of a special matrix

I have the following question:
Is there a closed formula for the elementary divisors of the Matrix
$M=\lbrace (m_{ij})\rbrace_{i=1,...,n,\ j=1,...,k}$, where $m_{ij}$ is the greatest common ...

**8**

votes

**2**answers

264 views

### Ideal Membership without Certificate?

I have a homogeneous ideal $I=\langle f_1,\ldots,f_r\rangle$ of the polynomial ring $\mathbb C[X_1,\ldots,X_n]=:R$ where each of the $f_i$ is actually over $\mathbb Z$. My computations are usually ...

**2**

votes

**2**answers

428 views

### What structure has been found for functions with this relationship.

Given $f$ and $g$
$\forall x y. f(x) = f(y) \Longrightarrow f(g(x)) = f(g(y))$
Or equivalently
$ker\ f \subseteq ker\ (f \circ g)$.
Note: if $f$ is injective then this holds for any $g$.
...

**0**

votes

**0**answers

243 views

### An interesting version of the problem “balls into bins”

Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...

**12**

votes

**0**answers

345 views

### Splay trees and Thompson's group $F$

( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but:
Question: Is there a reformulation of the Dynamic ...

**1**

vote

**0**answers

96 views

### Schönhage's SMM with only one instruction

It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...

**3**

votes

**2**answers

211 views

### Smallest base to reach partial recursive functions as a closure of unbound search

It is customary to define the class of partial recursive functions by taking the set of primitive recursive functions $PR$ and taking closure over unbound search operation.
Do we need the "whole" set ...

**19**

votes

**2**answers

973 views

### Expected edit distance

The edit or Levenshtein distance between two strings is the minimum number of single symbol insertions, deletions and substitutions to transform one string into another. For example ...

**1**

vote

**1**answer

385 views

### Distance between vertices in a vertex transitive graphs. [closed]

Can anybody help me in finding out the distances between vertices in a vertex transitive graphs. Is there any specific formula to calculate distance between vertices in this graph. Thanks for your ...

**12**

votes

**6**answers

2k views

### Giving $Top(X,Y)$ an appropriate topology

I am not sure if its OK to ask this question here.
Let $Top$ be the category of topological spaces. Let $X,Y$ be objects in $Top$.
Let $F:\mathbb{I}\rightarrow Top(X,Y)$ be a function (I will ...

**1**

vote

**1**answer

200 views

### Hypothesis: interaction-based model for λKβη

We are looking for a proof or counter-examples to the following
Hypothesis. In interaction calculus $\langle \varnothing\ |\ \Gamma(M, x) \cup \Gamma(N, x)\rangle \downarrow \langle \varnothing\ |\ ...

**3**

votes

**0**answers

166 views

### Is it possible to implement η-reduction in interaction nets?

There are several ways to encode λ-terms in interaction nets; for instance, using the original optimal algorithm by Lamping, or compiling λ-calculus into interaction combinators. However, all the ...

**1**

vote

**0**answers

112 views

### Turing-complete primitive interaction systems

Let us call primitive an interaction system with the signature
$\Sigma = \{(\rho, 0), (\xi, n)\}, \quad n \geq 2;$
and the only rule being of the form
$\rho \bowtie \xi[\rho, \xi(a_1, \dots , a_n), ...

**2**

votes

**1**answer

163 views

### Grzegorczyk-hierarchy, growth-rate and functions with finite image

Grzegorczyk-hierarchy divides primitive recursive functions in distinct classes with respect to their growth-rate. It seems that the higher we go the hierarchy, the more tools we have to define ...

**0**

votes

**1**answer

219 views

### Deriving the fundamental equation (with regards to computer vision)

I'm having a hard time understanding how a few equations are being derived. So the fundamental equation is an equation that relates corresponding points in stereo images. Anyway, that's the basic ...

**6**

votes

**2**answers

316 views

### Rigorous numerics for maxima and minima (one variable)

Let $f:\mathbb{R}_0^+\to \mathbb{R}$ be defined by some combination of the four basic operations and square roots. (The argument of square-roots is assumed is to be non-negative, and the value of ...

**3**

votes

**2**answers

632 views

### Turing-complete primitive blind automata

Let $N$ be the set of natural numbers, $S$ be the set of finite binary sequences, and
$Q = [N \rightarrow N] \times [N \rightarrow N],$
where $[N \rightarrow N]$ is the set of all computable ...

**2**

votes

**1**answer

188 views

### Reducing the error of Algorithms by assigning variables formulas instead of values

Let me first give the intuition for my question: Suppose that you want to use a ruler to mark $n$ points in a line on a page, with 1 cm distance between neighbor points. There are two ways:
1- Mark ...

**3**

votes

**1**answer

635 views

### Collatz conjecture— finite state machine transducer construction, origination?

wikipedia has an entry on the Collatz conjecture with a section on As an abstract machine that computes in base two. this apparently describes a construction of a FSM transducer computing sequential ...

**6**

votes

**1**answer

426 views

### Is equality of terms for “real” numbers with roots, logarithm, exponential, sin, cos, and other trigonometric operations decidable with a Turing-machine?

If yes, how? Also, I know you can't do it for arbitrary statements about real numbers, but that's not what I'm asking, and by "real" numbers, I mean the numbers constructible from 1, -, /, and the ...

**3**

votes

**2**answers

1k views

### How to draw Archimedean-Galileo spiral?

It is known that some plane curves can be drawn with a tool. For instance, I heard at a web site that Archimedes created his spiral in the third century B.C. by fooling around with a compass and ...