# Tagged Questions

The tag has no usage guidance.

62 views

94 views

### Is this question $NP_R$ hard?

Consider $n$ variables $x_1, \cdots, x_n$ and $f=\sum a_i x_1^{d_{i1}}\cdots x_n^{d_{in}}$ such that for each $i$, $d_{i1}+\cdots+d_{in}=d$ for some fixed $d$ and $a_i\geq 0$. I am interested in the ...
206 views

### Uniformity vs. nonuniformity in algebraic complexity theory

I understand that the study of Boolean circuits and nonuniform complexity classes was introduced to (hopefully) prove separation of uniform complexity classes. In this sense, nonuniform computational ...
264 views

### Foundational textbook(s) for Complexity and Computability on Real Numbers

It would be extremely helpful if someone can suggest foundational textbooks on Recursive Analysis (Computability over Reals) which explains connections between Computability and the Topological ...
321 views

### Computing Functions with Dynamical Systems

I was trying to make a set of differential equations "compute" some given function just like a Turing Machine does. Essentially, a given Turing Machine with an initial configuration (which includes ...
4k views

### Is it possible to test if a computable number is rational or integer?

Is it possible to algorithmically test if a computable number is rational or integer? In other words, would it be possible for a library that implements computable numbers to provide the functions <...
289 views

### Oracle complexity of a problem in the Counting Hierarchy

In "On The Complexity of Numerical Analysis" (SIAM J. Comp. Vol. 38, 2009), Allender et al. introduce the problem of PosSLP and show that its complexity lies in the counting hierarchy, and more ...
272 views

### Concerning decidability of a problem on real numbers [closed]

This question is an outgrowth of a certain maths problem I've been thinking about. Suppose you use an oracle to represent a real number. The oracle is of the following form: you give it an integer ...
What is the complexity (on the standard integer RAM) of computing the standard discrete Fourier transform of a vector of $n$ integers? The classical algorithm for fast Fourier transforms, ...