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

350

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

10

votes

1

answer

313

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

340

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,808

3

6

votes

0

answers

311

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

2

5

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,454

4

votes

0

answers

185

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,039

4

votes

1

answer

72

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,039

4

votes

1

answer

231

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

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,039

2

votes

1

answer

146

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.2k

2

votes

0

answers

48

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,039

2

votes

0

answers

107

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,039

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 205

1

vote

0

answers

66

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,039

1

vote

1

answer

252

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

1

vote

1

answer

156

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

112

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,039

1

vote

1

answer

141

views

Is the relation decidable?

computability algebra

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

1

vote

1

answer

160

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,264

1

vote

2

answers

128

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

vote

0

answers

103

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,039

0

votes

1

answer

77

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,808

0

votes

1

answer

84

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

-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,308

-2

votes

1

answer

152

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,039

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

26 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?

Is Hartmanis-Stearns conjecture settled by this article?

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

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

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]

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

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?

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?

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

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

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

Complexity class on quantum computation and classic ones