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
37
votes
12
answers
3k
views
Interesting conjectures "discovered" by computers and proved by humans?
There are notable examples of computers "proving" results discovered by mathematicians, what about the opposite:
Are there interesting conjectures "discovered" by computers and proved by humans?
...
CommunityBot
- 1
1
vote
0
answers
169
views
Determine existence of matroid with some barrier given
Let $E$ be a finite ground set. Let $\mathcal{L}$ (as lower barrier) and $\mathcal{U}$ (upper) be subsets of $2^E$. How can we determine whether there is some matroid $\mathcal{M}=(E,\mathcal{I})$ ...
- 121
5
votes
1
answer
453
views
an algebraic variety for a boolean circuit
There is a polynomial reduction from a $3-CNF$ $SAT$ problem to some system of polynomial equations over $\mathbb{F}_2$.
I mean there is polynomial reduction $F$ such that for every boolean ...
CommunityBot
- 1
7
votes
5
answers
16k
views
Prove a function is primitive recursive
Hey,
I'm taking a course in computability theory, but I'm struggling with primitive recursion. More specifically we are often asked to prove that some arbitrary function is primitive recursive, but I ...
1
vote
2
answers
290
views
Practical permutation search problems resilient to backtrack techniques
I asked a similar question here: Permutation search problems with no known $o(n!)$ algorithms; to which one-way functions over a space of permutations gives a problem with no $o(n!)$ solution (...
CommunityBot
- 1
1
vote
0
answers
123
views
Expressing Numbers with a Minimal Sum in Powers of 2 [closed]
The first 64 bits of pi are:
11.00100100001111110110101010001000100001011010001100001000110100
Computer multiplication can be sped up by looking for patterns and ...
- 1,547
3
votes
1
answer
1k
views
How to get $\omega$-regular expression from buchi automaton
Is there an algorithm or a trick on how to get $\omega$-regular expressions from Buchi automatons? If yes, is there also some way to do create minimal such regular expressions?
It is extremely ...
- 236k
5
votes
2
answers
500
views
How to construct particular De Bruijn sequences
For $n \ge 2$, there is at least one binary DeBruijn sequence beginning with $n$ zeros followed by $n$ ones. Is there a straightforward way to construct such a sequence for each $n \ge 2$? Examples:
...
- 12.3k
-1
votes
1
answer
1k
views
Transition Graph per alphabet? [closed]
How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from ...
CommunityBot
- 1
5
votes
2
answers
277
views
What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space?
The question is mostly in the title:
What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space?
Imagine I have some non-convex polyhedron $P$, and I would like to ...
CommunityBot
- 1
3
votes
0
answers
263
views
"Kolmogorov complexity" of models of computation
This question was partly inspired by my learning about John Tromp's binary lambda calculus and similar minimal languages such as Jot. A more detailed discussion of some of these ideas is in Michael ...
- 3,612
2
votes
1
answer
2k
views
Composite finite-state machines
A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...
CommunityBot
- 1
5
votes
0
answers
240
views
Complexity of approximating the size of the range of a matrix
Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define:
$$S_M = |\{Mx : x \in \{-1,1\}^n\}.$$
It is NP-hard to compute $S_M$ exactly I believe by applying the ...
CommunityBot
- 1
13
votes
2
answers
14k
views
All-pairs shortest paths in trees?
This is a reference request, since I'm sure what follows isn't new, but I can't seem to find it.
Suppose that we have a finite tree $T$ with non-negative weights on the edges. Naively, computing the ...
- 13.2k
28
votes
8
answers
4k
views
Between mu- and primitive recursion
It is well known that primitive recursion is not powerful enough
to express all functions, Ackermann function being probably the best
known example.
Now, in the logic courses (that I have had look at)...
- 32.5k
7
votes
0
answers
423
views
Does the Mandelbrot set have infinite VC dimension?
Define a binary classifier for points in the complex plane, whose parameter $\theta$ is an isometry of $\mathbb{C}$, and which classifies $z \in \mathbb{C}$ based on whether or not $\theta(z)$ is in ...
- 445
9
votes
1
answer
2k
views
Efficient SVD of a matrix without some of the columns
I have a matrix $A \in \mathbb{R}^{p \times q}$ of rank $r$ and its SVD decomposition, i.e,
$$
A = U S V^\top,
$$
where $U \in \mathbb{R}^{p \times r}$ and $V \in \mathbb{R}^{q \times r}$ are ...
- 341
2
votes
2
answers
624
views
Time Hierarchy Theorem and P vs NP
One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...
- 11
5
votes
1
answer
220
views
Monoidal cats and string diagrams for a semantics of object oriented programming languages
It seems to me that in a statically typed, object oriented language, there is a striking similarity to wiring diagrams. Wires (objects) of type $X$ go into functions (boxes) of input type $X$. Is ...
- 3,249
6
votes
0
answers
217
views
Nonclassical polynomials, circles, and groups
Tao and Ziegler have introduced a generalization of polynomials over a prime field called nonclassical polynomials, useful for studying the Gowers norm.
A nonclassical polynomial of degree $d$ is a ...
- 539
18
votes
1
answer
1k
views
Is it possible to make an algorithm that could predict the likelihood that a program will halt?
Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...
- 19.6k
3
votes
1
answer
404
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 $\beta$-...
CommunityBot
- 1
16
votes
2
answers
816
views
Can a stochastic Turing machine output a consistent extension of PA with positive probability?
Suppose that we interpret the output tape of a Turing machine as an assignment of true or false to all sentences of PA, taking the $n$th output bit as the truth value of the sentence with Goedel ...
- 24.8k
14
votes
2
answers
4k
views
Best-case Running-time to solve an NP-Complete problem
What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman is $O(n!)$, but with dynamic programming it can be done ...
- 141
0
votes
2
answers
1k
views
What is a maximal set in the context of argumentation in AI [closed]
I am computer scientist, not a mathematician, I've been reading some papers on argumentation in AI that uses the term 'maximal' set without defining it. I think it's left undefined because it's a ...
- 32.5k
4
votes
1
answer
176
views
What class of probability distributions do probabilistic turing machines induce? [closed]
What class of probability distributions is induced by the class of probabilistic turing machines? Is there a precise characterization?
- 6,287
15
votes
0
answers
425
views
Complexity classes for BSS machines
Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where
Cells on the tape can hold arbitrary elements of $\mathcal{S}$.
The ...
CommunityBot
- 1
6
votes
1
answer
1k
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 NP$-...
CommunityBot
- 1
0
votes
0
answers
780
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 ...
- 19.6k
1
vote
0
answers
112
views
Canonical representation of binary decision trees in Ptime?
I am wondering about the possibility of efficiently (here: in Ptime) representing binary decision trees (BDT) by some other data structure in a way that characterizes their equivalence.
More ...
CommunityBot
- 1
3
votes
1
answer
382
views
Equivalence between Diffie Hellman and Discrete Log
For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent?
Is there any group for which we suspect them to be different?
Could there be a finite ...
- 25.4k
1
vote
0
answers
59
views
Open volumetric time series data set
Does anyone know where I can find a good open volumetric time series data set?
I had a look at some of Stanford's open data sets (https://graphics.stanford.edu/data/voldata/ )
But these do not seem ...
- 19.6k
7
votes
1
answer
304
views
"Separated" version of Sauer's lemma on VC classes
Sauer's lemma, a well-known result in computational complexity theory, learning theory, and combinatorics, states the following:
Let $\Phi$ be a collection of subsets of a set $U$, and assume that ...
- 2,207
1
vote
0
answers
137
views
Optimal reduction using token-passing nets
I am looking for implementation of optimal reduction for λ-calculus based on interaction nets (McCarthy's amb allowed) in the spirit of "Token-Passing Nets: Call-by-Need for Free" by François-Régis ...
3
votes
1
answer
446
views
floating point representation via the perspective of TTE/computable analysis
Floating point numbers are not compatible with the usual theory of type 2 theory of effectivity (TTE), and not even the real-RAM model; there are functions that are computable in one model but not ...
- 6,287
11
votes
6
answers
5k
views
Aren't "oracle machines" unsound concepts? [closed]
From Wikipedia (bold emphasis at the end is mine):
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a ...
- 6,132
19
votes
0
answers
782
views
Reference request: Parallel processor theorem of William Thurston
Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...
- 15.4k
-1
votes
1
answer
550
views
Are limits decidable? Should definitions be decidable? [closed]
This question is about the Turing computability of the $\epsilon-N$ definition of a limit of an infinite sequence $S$. First, a proposition:
There cannot exist a Turing Machine $M$ which, given a ...
- 718
4
votes
0
answers
311
views
Possible $\mathsf{NP}$ complete problem from number theory
A candidate $\mathsf{NP}$ complete variant of factoring was posted in https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring, where decision problem $\text{BOUNDED-...
CommunityBot
- 1
5
votes
2
answers
227
views
If $f : [-a,a] \rightarrow \mathbb{IR}$ is Scott continuous, why are $f^-$ and $f^+$ measurable?
In "A domain theoretic account of Picard's theorem" (http://www.doc.ic.ac.uk/~dirk/Publications/icalp2004.pdf), the authors assert the following.
Let $\mathbb{IR}$ be the interval domain $\lbrace [a^-...
- 48.9k
6
votes
0
answers
690
views
Unique Nash equilibrium games
Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...
- 399
1
vote
1
answer
3k
views
Finding t vlaue in Bezier curve [closed]
According to this question, I'm looking for some method to find the t value in Quadratic bezier curve equation:
$$
B(t)=P_0+t(1-t)P_1+t^2P_2 \space \space where \space 0 ≤ t ≤ 1
$$
In this ...
CommunityBot
- 1
6
votes
1
answer
239
views
Algorithm that generates a n-simplex that cover n-polytope?
Given an $n$-cube with unit volume, is there any algorithm that generates a $n$-simplex that covers the $n$-polytope?
- 161
24
votes
3
answers
2k
views
What technical and/or theoretical challenges are involved in automatically extracting proofs from books and papers into Coq code?
Over the years, advances in machine learning has allowed us to communicate and interact, using the same natural language, more and more semantically with computers, e.g. Google, Siri, Watson, etc. On ...
7
votes
0
answers
245
views
Distribution of trivial subset sums
Suppose I have a set $S$ of $n$ integers picked independently, uniformly at random from $[-L, L].$ Let $z(S)$ be the number of subsets of $S$ which sum to zero. The question is: what is the ...
- 96.4k
15
votes
3
answers
2k
views
Why does the bitxor function appear in Nim?
I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum ...
CommunityBot
- 1
24
votes
4
answers
3k
views
does the "convolution theorem" apply to weaker algebraic structures?
The Convolution Theorem is often exploited to compute the convolution of two sequences efficiently: take the (discrete) Fourier transform of each sequence, multiply them, and then perform the inverse ...
- 43
1
vote
1
answer
432
views
Functional programing and intensional type theory
I know very little about how computers work, so please excuse my ignorance!
I think of the Glasgow Haskell Compiler as a program that eats up extensional type theory and spits out a program which ...
- 66.8k
3
votes
0
answers
243
views
Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem
Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...
- 47.3k
-4
votes
1
answer
238
views
What exactly is wrong with this statement (Lucas-Penrose fallacy)? [closed]
Statement
"For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method."
...
