User XL _At_Here_There

7

13

votes

1

answer

1k

views

Entropy and computational complexity

Feb 2 '18 at 10:15 Community♦ 1

2

11

votes

2

answers

358

views

How to judge the definition of computational complexity of reals is natural or suitable?

cc.complexity-theory reference-request computability computing-over-reals computable-analysis

Nov 26 '14 at 8:50 Kaveh 21.1k

10

votes

1

answer

317

views

Hartmanis-Stearns conjecture and the computable transcendental numbers

cc.complexity-theory reference-request examples

Jan 3 '15 at 20:10 argentpepper 2,241

1

9

votes

2

answers

348

views

Any computable transcendental number that is computable in P time but not $O(n)$

cc.complexity-theory comp-number-theory

Jul 5 '17 at 23:40 Jeffrey Shallit 6,878

3

6

votes

0

answers

313

views

Is there any algorithm outputing $e$ in real time?

cc.complexity-theory reference-request nt.number-theory comp-number-theory

Jan 4 '18 at 22:00 Joshua Grochow 34.6k

4

votes

0

answers

186

views

What is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$

cc.complexity-theory reference-request comp-number-theory

Nov 18 '17 at 12:13 XL _At_Here_There 1,005

2

4

votes

1

answer

1k

views

Is Hartmanis-Stearns conjecture settled by this article?

cc.complexity-theory co.combinatorics computability automata-theory nt.number-theory

Oct 5 '17 at 9:26 J.-E. Pin 4,641

4

votes

1

answer

246

views

Is it decidable that a computable analytic function over $\mathbb{R,C} ,$ equals $0$

reference-request computability computable-analysis model-theory

Nov 24 '14 at 13:11 Andrej Bauer 25.6k

3

votes

0

answers

75

views

How to charactorize computational complexity based on finding solution to algebraic equations? [closed]

reference-request complexity-classes universal-computation comp-number-theory computational-mathematics

Jan 9 '18 at 2:47 XL _At_Here_There 1,005

3

votes

1

answer

73

views

Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?

cc.complexity-theory computability automata-theory combinatorics

Oct 12 '17 at 6:24 XL _At_Here_There 1,005

2

votes

0

answers

49

views

Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?

complexity-classes computational-geometry

Nov 4 '17 at 12:12 XL _At_Here_There 1,005

2

votes

0

answers

110

views

What is the complexity of computation of zero point by Rieman zeta function?

cc.complexity-theory complexity-classes comp-number-theory

Jul 4 '17 at 17:04 XL _At_Here_There 1,005

2

votes

0

answers

141

views

Can the definition of ambiguity of CFG be extended to CSG?

fl.formal-languages

Jun 17 '14 at 6:38 XL _At_Here_There 1,005

1

vote

0

answers

203

views

anything hinting that EXPTIME $\subseteqq$ PSPACE?

cc.complexity-theory complexity-classes exp-time-algorithms pspace

Mar 29 at 10:59 XL _At_Here_There 1,005

1

vote

0

answers

171

views

What is the computational complexity of the fastest algorithm to compute Jordan canonical form for a matrix

complexity computational-mathematics

Mar 7 at 2:31 XL _At_Here_There 1,005

1

vote

1

answer

152

views

The decision procedure of theory of closed real field is in NP-hard?

cc.complexity-theory np-hardness complexity-classes computational-geometry

Dec 21 '19 at 7:32 David Eppstein 49.9k

1

vote

0

answers

88

views

What is the relation between computational complexity of algebraic number and computational complexity to find the solution to algebraic equation?

algebraic-complexity

May 6 '18 at 16:55 Glorfindel 211

1

vote

0

answers

68

views

Relating classes of computational complexity to finding solution to classes of algebraic equations [closed]

cc.complexity-theory reference-request algebraic-complexity

Jan 13 '18 at 0:50 XL _At_Here_There 1,005

1

vote

1

answer

270

views

Relation between transcendental numbers and computational complexity?

reference-request complexity-classes nt.number-theory comp-number-theory

Jan 10 '18 at 6:18 Joshua Grochow 34.6k

1

vote

1

answer

158

views

What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$

complexity-classes algebraic-complexity

Nov 21 '17 at 15:37 Community♦ 1

1

vote

1

answer

124

views

Set of languages that can represent every c. e. languange

fl.formal-languages computability automata-theory

Oct 14 '17 at 11:45 XL _At_Here_There 1,005

0

votes

1

answer

141

views

Is the relation decidable?

computability algebra

Oct 8 '17 at 6:03 Bjørn Kjos-Hanssen♦ 4,318

0

votes

1

answer

169

views

Is Buchberger's algorithm or Wu's method valuable theoretically when we have the Tarski–Seidenberg theorem?

decidability automated-theorem-proving proof-assistants

Oct 3 '17 at 20:35 Sylvain 3,304

0

votes

2

answers

130

views

Where can I find the proof of the theorem and what is the computational complexity of the computably isomorphic map?

cc.complexity-theory reference-request computability computable-analysis

Dec 12 '14 at 1:13 Community♦ 1

-1

votes

1

answer

91

views

What is the relation between P-immune languages and NP-complete languages? [closed]

complexity-classes fl.formal-languages computability

Oct 16 '17 at 1:34 Bjørn Kjos-Hanssen♦ 4,318

-1

votes

1

answer

80

views

Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?

complexity-classes fl.formal-languages computability automata-theory

Oct 10 '17 at 11:49 Jeffrey Shallit 6,878

-1

votes

1

answer

85

views

For two representations of finite length of one computable number are there $P$-time algorithms that compute one from another

cc.complexity-theory reference-request computable-analysis

Dec 10 '14 at 8:42 Tom van der Zanden 533

-2

votes

1

answer

159

views

Complexity class on quantum computation and classic ones

cc.complexity-theory quantum-computing

Nov 11 '17 at 2:57 XL _At_Here_There 1,005

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

28 Questions

Entropy and computational complexity

How to judge the definition of computational complexity of reals is natural or suitable?

Hartmanis-Stearns conjecture and the computable transcendental numbers

Any computable transcendental number that is computable in P time but not $O(n)$

Is there any algorithm outputing $e$ in real time?

What is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$

Is Hartmanis-Stearns conjecture settled by this article?

Is it decidable that a computable analytic function over $\mathbb{R,C} ,$ equals $0$

How to charactorize computational complexity based on finding solution to algebraic equations? [closed]

Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?

Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?

What is the complexity of computation of zero point by Rieman zeta function?

Can the definition of ambiguity of CFG be extended to CSG?

anything hinting that EXPTIME $\subseteqq$ PSPACE?

What is the computational complexity of the fastest algorithm to compute Jordan canonical form for a matrix

The decision procedure of theory of closed real field is in NP-hard?

What is the relation between computational complexity of algebraic number and computational complexity to find the solution to algebraic equation?

Relating classes of computational complexity to finding solution to classes of algebraic equations [closed]

Relation between transcendental numbers and computational complexity?

What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$

Set of languages that can represent every c. e. languange

Is the relation decidable?

Is Buchberger's algorithm or Wu's method valuable theoretically when we have the Tarski–Seidenberg theorem?

Where can I find the proof of the theorem and what is the computational complexity of the computably isomorphic map?

What is the relation between P-immune languages and NP-complete languages? [closed]

Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?

For two representations of finite length of one computable number are there $P$-time algorithms that compute one from another

Complexity class on quantum computation and classic ones