Questions tagged [computer-science]
For question borderline with, or having application to, computer science. Consider also posting http://cs.stackexchange.com/ or http://cstheory.stackexchange.com/ instead of here, if appropriate.
641 questions
3
votes
2
answers
790
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 ...
CommunityBot
- 1
2
votes
1
answer
286
views
Universality of blind graph rewriting
Let us consider $S(M) = \{(f_0, f_1) | f_0, f_1: M \rightarrow M\}$, where $M$ is a finite set. Each element of $S(M)$ is equivalent to a finite directed
graph with the set of nodes $M$, which has ...
1
vote
1
answer
676
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 ...
- 11.2k
3
votes
0
answers
266
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 ...
3
votes
2
answers
912
views
Why is every finite set Diophantine? [closed]
I understand that every finite set is recursively enumerable, as I see that one could just encode each element of some finite set on a Turing Machines tape, and then have the machine check each member ...
- 3,094
2
votes
0
answers
147
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), ...
3
votes
1
answer
249
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 ...
- 73.2k
0
votes
1
answer
312
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 ...
- 188k
7
votes
2
answers
372
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 ...
- 20.2k
2
votes
1
answer
216
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 ...
- 142
25
votes
4
answers
3k
views
Algorithmically unsolvable problems in topology
This question is inspired by a paper by B. Poonen that appeared on the arxiv some time ago: http://arxiv.org/abs/1204.0299. The paper gives a sample of algorithmically unsolvable problems from various ...
- 5,309
38
votes
0
answers
1k
views
Computer calculations in A_infinity categories?
Is there a good computer program for doing calculations in A-infinity categories?
Explicit calculations in A-infinity categories are an important, useful, yet very tedious task. One has to keep track ...
CommunityBot
- 1
7
votes
1
answer
799
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 ...
- 32.5k
4
votes
1
answer
967
views
Algebraic structure generated by primitive graph operations
Let $M$ be a finite set, and
$S(M) = \{(f_0, f_1) | f_0, f_1: M → M\}$.
Each element of $S(M)$ can be considered as a finite directed graph with the set of nodes $M$, which has exactly two arrows ...
12
votes
1
answer
1k
views
Characterization of Boolean-valued functions on the discrete cube based on its Fourier coefficients.
Consider functions on the discrete cube $\{-1,1\}^n$.
We consider the Discrete Fourier Transform of such functions. Suppose we denote the parity function on a subset $S \subseteq [n]$ of co-...
- 1,989
5
votes
0
answers
139
views
Are there sampNP-intermediate problems?
This questions is approximately cross-posted from theoretical computer science stackexchange
Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} \...
CommunityBot
- 1
3
votes
2
answers
776
views
Certain type of regular languages
Dear All,
there is one type of regular languages, over $\{a,b\}$, which appear naturally in what I am studying, so if anybody could recognise them, or say any sort of their characterisation, that ...
CommunityBot
- 1
5
votes
1
answer
2k
views
Non-uniform complexity of the halting problem
This question is approximately cross-posted from Theoretical Computer Science Stack Exchange: https://cstheory.stackexchange.com/questions/14445/complexity-of-the-halting-problem
What can be said ...
CommunityBot
- 1
2
votes
1
answer
211
views
Is there research on the notion of co-accessibility?
I want to start off with a disclaimer that I am only a mathematical amateur. Please forgive me for ignorance or any non-standard nomenclature I use here :)
Let's start off with some context.
Let X ...
- 8,842
3
votes
1
answer
175
views
fast approximate k-nearest neighbors in high dimensions?
Hi, I've been scanning the literature trying to find an adequate approximate k-neighbour for my outlandish data set, but I remain stymied. Perhaps someone can help?
The dataset is huge, both in ...
- 31
2
votes
0
answers
246
views
A primal-dual (double) circle packing (coin graph) question
I know that any 3-connected simple planar graph with a designated outside face (outer face) has a primal-dual (double) circle packing (Brightwell-Scheinerman Theorem).
Q1- But I am not sure whether ...
- 6,711
1
vote
0
answers
393
views
The used symbols for equality and equivalence
Background: I am currently developing a general purpose programming language which allows formal verification (i.e. correctness proofs) of programs. During the development it came out that a lot of ...
- 165
11
votes
0
answers
556
views
Various definitions of recursion from ordinal machines
Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...
- 32.5k
6
votes
2
answers
609
views
What categories correspond to the typed lambda calculus with parametric types?
the unadorned typed lambda calculus correspond to the closed cartesian categories, but if we add in dependent or parametric types how are they then characterised?
- 48.8k
3
votes
0
answers
516
views
Groupoid interpretation of type theory
Hello,
I read the paper on groupoid interpretation of type theory by Hofmann and Streicher and I have a question. According to the authors $Tm([[\text{Set}\:[\Gamma]\: ]])$ is the same as $\text{Se}([...
- 53.3k
1
vote
1
answer
310
views
Counterexamples for this algorithm for recognizing lexicographic product of graphs?
Found a possible reduction from recognizing lexicographic product of graphs to 2SAT
(since 2SAT is polynomial, the algorithm is polynomial).
Can't prove completeness of the algorithm and since it is ...
- 25.4k
0
votes
0
answers
98
views
Exact Length Problem in a directed graph
I have a directed graph that consist of N^2 vertices (like a square) and each vertex is connected to at most 1 node (not bidirectional) and every connections have length 1. There are no cycles in the ...
4
votes
1
answer
2k
views
Deciding equivalence of regular languages
Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows:
build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) =...
- 38.6k
0
votes
1
answer
413
views
Is there any relationship between a tree(graph theory) and semi-metric?
suppose we have a tree(undirected) with $n$ vertices.The edges are weighted(distances). Is it possible to impose a semi-metric structure on the graph using these distances and adjacency matrix?
CommunityBot
- 1
11
votes
3
answers
2k
views
Higher categories as data structures
Still wading through higher category theory. I find the subject a bit intimidating, not so much for technical reasons, but because I lack sufficient intuition as to the motivation(s)/heuristics one ...
- 9,627
7
votes
1
answer
951
views
Who introduced the concept of Primitive recursive functions?
I have thought that Gödel introduced the concept of Primitive recursive functions in his seminal paper "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme" (I hope I ...
- 1,599
7
votes
0
answers
172
views
Finding a database of representations as matrices
Sorry if this would be more appropriate as a stackoverflow and not a mathoverflow question, but I think it's more likely to be known in this community.
There are plenty of places on the internet or ...
- 7,952
8
votes
0
answers
1k
views
Question on randomness extractors
Person A has a source $W$ with min-entropy($W$) = $k$. He also has an extra piece of information about the random source, denoted with $y$, such that min-entropy($W|y$) = $k/3$.
The adversary doesn't ...
- 5,502
3
votes
1
answer
1k
views
#P version of SUBSET SUM
The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...
CommunityBot
- 1
5
votes
0
answers
326
views
Büchi automata with acceptance strategy [closed]
I have already asked this question on cstheory.stackexchange, but without success. Maybe it is too close to an "open problem", although it is not a famous one. Anyway I try here, I can ...
CommunityBot
- 1
2
votes
1
answer
848
views
Algorithm for satisfiability of inequalities.
I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$.
In ...
- 37.7k
0
votes
0
answers
613
views
Examples of Hamiltonian Cycle Problem / Traveling Salesman Problem in general grid graph form
I understand that there is a polynomial algorithm to solve TSPs that are in solid grid graph form (grid graphs without holes).
I am particularly interested in the non-solid grid graph form of the ...
- 45
12
votes
3
answers
877
views
Alive dynamical system
Intuitively, one can say that a dynamical system is alive if one can build a universal Turing machine inside.
So, Conway's Game of Life is alive and shift space should be dead.
I fail to make this ...
CommunityBot
- 1
5
votes
2
answers
3k
views
symmetric difference of languages - both are in NP and coNP
I have this problem,
Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like:
$L_1 \oplus L_2$ = {x | x is in exactly one of $...
- 47.3k
3
votes
2
answers
2k
views
Kleene's fixed point theorem on recursive subsets of computable functions
I have a question about the possibility to apply/restate the Kleene fixed point theorem on recursive subsets of computable functions. I don't know if this is trivial and/or if related questions have ...
- 236k
5
votes
1
answer
470
views
Arrangement of integers 1..k^2 in k*k grid to minimize energy function
Question arises from considering cache oblivious algorithms.
What is the optimal way arrange the numbers $1$ to $k^2$ in a grid, to minimize to average difference between any two neighbouring squares?...
- 13.4k
2
votes
0
answers
119
views
How to argue about state transitions?
Computing differs from math by its dependence on state changes, among other things. A program can be seen as a composition of state transitions, and it would be nice to have an inverse function to ...
1
vote
2
answers
686
views
Is there constructive proof of the fact that every recursive set $A \ne \varnothing$ is recursively enumerable in non-decreasing order?
Every proof I've read about this fact considers two cases: $A$ - finite and $A$ - infinite but this is undecidable problem. So, is there constructive proof?
- 14k
7
votes
2
answers
955
views
Distribution of the computable numbers on the real number line
If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...
CommunityBot
- 1
8
votes
2
answers
636
views
Reduction rules for inductive types
(I'm not sure if I should post this here rather than at Theoretical Computer Science, I've found a lot of type theory related questions on MathOverflow)
I'm working in Martin-Löf type theory with ...
CommunityBot
- 1
0
votes
1
answer
167
views
Subset-Free Codes
For each non-negative integer $n$, what antichain(s) in $\{0,1\}^n$ with the pointwise partial order: $\;\;$ 1. $\;$ have the most elements $\;\;$ 2. $\;$ minimize the maximum of its elements' sum of ...
- 73.2k
-1
votes
2
answers
1k
views
Travelling Salesman Problem [closed]
Does there exist an instance of the travelling salesman problem where the optimal solution has edges that cross?
CommunityBot
- 1
9
votes
4
answers
838
views
Characterizing a tumbling convex polytope from the surface areas of its two-dimensional projections
My general question concerns what we can learn about an arbitrary, three-dimensional convex polytope (or convex hull of an arbitrary polytope) strictly from the surface areas of its two-dimensional ...
- 151k
25
votes
1
answer
6k
views
Evidence for integer factorization is in $P$
Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...
- 16.8k
5
votes
1
answer
2k
views
Decomposition of a complete graph into maximal matching subgraphs
Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge?
For example, consider $K_4$ with vertices $V=${1,2,3,4}...
- 39.9k