**8**

votes

**1**answer

558 views

### How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?

Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient
algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that
$n = \sum_{i=1}^k a_i m_i$?
...

**6**

votes

**3**answers

468 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 ...

**20**

votes

**4**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

104 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$ ...

**8**

votes

**1**answer

309 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

326 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

345 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

420 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 ...

**1**

vote

**0**answers

76 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

89 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

803 views

### Kolmogorov complexity is the strongest noncomputable function

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

**4**

votes

**1**answer

317 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

80 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 ...

**10**

votes

**2**answers

558 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

237 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

388 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

147 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 ...

**8**

votes

**2**answers

352 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, ...

**1**

vote

**0**answers

120 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

162 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

95 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

300 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

297 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)$ ...

**11**

votes

**4**answers

438 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 ...

**13**

votes

**2**answers

1k 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

147 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

388 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$, ...

**13**

votes

**3**answers

652 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

235 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 ...

**2**

votes

**0**answers

55 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

147 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

214 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

419 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

198 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

312 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

93 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

194 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 ...

**18**

votes

**2**answers

883 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

262 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 ...

**8**

votes

**6**answers

1k 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

193 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\ |\ ...

**2**

votes

**0**answers

151 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

64 views

### Optimal Reduction in Interaction Calculus

We work in interaction calculus.
Let $\Sigma = \{\lambda, \psi, \delta, \epsilon\}$, $\text{Ar}(\lambda) = \text{Ar}(\psi) = \text{Ar}(\delta) = 2$, and $\text{Ar}(\epsilon) = 0$.
For any $\alpha ...

**1**

vote

**0**answers

108 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), ...

**1**

vote

**1**answer

148 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

200 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

270 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

554 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

167 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 ...

**1**

vote

**1**answer

537 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 ...