Bjørn Kjos-Hanssen
Moderator
  • Member for 11 years, 3 months
  • Last seen this week
Example where equivalence is easy but finding class representative is hard
1 votes

A famous example from descriptive set theory: Let us define an equivalence relation $\sim$ on $\mathbb R$ by $$r\sim s\iff r-s\in\mathbb Q.$$ This is a rather "easy" equivalence relation, in ...

View answer
Number of equivalence classes in regular languages as a function of DFA size
1 votes

Answer to Question 1, What is the smallest $n$ for which $|T/{\sim}|=|T|$? We have $$n=\max_{|w|=|x|=s,\\ w\ne x}\mathrm{sep}(w,x)$$ where $\mathrm{sep}(w,x)$ is the smallest number of states in ...

View answer
Examples of nontrivial non-discriminatory functions
Accepted answer
1 votes

Let $n=1$. Let $\mu$ be the usual Lebesgue length measure on $[1/2,1]$, and let $\mu$ be the negative of the usual Lebesgue length measure on $[0,1/2]$. In particular, Lebesgue measure is $|\mu|$. ...

View answer
Can we efficiently distinguish between P and BPP?
1 votes

You defined that algorithm $D$ distinguishes $BPP$ from $P$ if there exists a language $L \in BPP$ such that for all $A \in PTM$, $$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \...

View answer
Is true randomness and the physical Church-Turing thesis incompatible?
1 votes

In a way, if we imagine time continuing indefinitely then with probability 1, random numbers, obtained from I guess the collapse of the wave function in quantum mechanics, will form a non-computable ...

View answer
Are there proofs which show that AIs are bound to be "worse" than the human brain?
1 votes

I suppose the scientific consensus is that while we are very far from there, in principle a digital artificial intelligence could mimic a human intelligence. For some recent work on the Church-...

View answer
Is there any good and free Introduction to topological graph theory
1 votes

Archdeacon's survey Topological Graph Theory was almost mentioned already: http://www.math.u-szeged.hu/~hajnal/courses/PhD_Specialis/Archdeacon.pdf

View answer
Computational complexity in quantitative finance
1 votes

Predicting the stock market is hard! Can TCS make this sentiment more formal? If stocks are modeled as random variables like geometric Brownian motions then prediction becomes a concern of ...

View answer
Are aspects of the 20 questions game ambitious enough for graduate research?
1 votes

A PhD thesis should have references to the published literature and should be extending results in that literature. So it is important to be able to say, these serious researchers did something but ...

View answer
Al-Mubaid's Similarity Measure for Ontological Concepts
0 votes

There is a whole study of hierarchical clustering. You start with a discrete set of nodes and iteratively connect the ones that are closest according to some similarity measure. The branches of the ...

View answer
1 2
3