# Questions tagged [computing-over-reals]

The tag has no usage guidance.

46 questions
Filter by
Sorted by
Tagged with
175 views

### Complexity of the Partition problem in the Real RAM model

The Partition problem is: given $n$ numbers in the range $[0,M]$, decide if they can be partitioned into two subsets with equal sum. If the numbers are integers, then the problem is NP-complete, but ...
• 2,294
195 views

### What infinite sums cannot be approximated in polynomial time?

The following is from the book Geometric algorithms and combinatorial optimization: It shows an infinite sum that has an FPTAS (= an $\epsilon$-approximation can be computed using poly($1/\epsilon$) ...
• 2,294
106 views

### Maximum theoretical compression ratio for real-valued data

Given a sequence of $N$ real-valued vectors $\mathbf{v_1}, \mathbf{v_2}, ..., \mathbf{v_N}$, each of dimension $d$, do any of the below bounds exist? The minimum number of real-valued vectors of ...
511 views

### Deciding whether a convex region is empty

Let $S\subseteq \mathbb{R}^n$ be a convex region defined by $$g_i(x)\leq 0, ~~i\in 1,\ldots,m,$$ where $g_i$ are convex functions. The goal is to decide whether $S$ is empty, and if not - find a point ...
• 2,294
191 views

### Computing an approximate root of a two-dimensional monotone function

Let $f$ be a Lipschitz-continuous function from the square $[-1,1]^2$ to itself, satisfying the following conditions: For all $y\in [-1,1]$: $~~~~f(-1,y)_1\leq 0\leq f(1,y)_1$, and $f(x,y)_1$ is ...
• 2,294
41 views

### Statements equivalent to strongly polynomial time linear programming

Say a problem is SPT iff it admits an SPT algorithm. What statements of interest are known to be equivalent to "LP is SPT"? Examples: "linear feasibility solving is SPT" (due to ...
• 672
1 vote
158 views

319 views

### Zero of a multivariate cubic equation

Given a multivariate cubic equation $f(\vec{x})$ over reals where all coefficients of $f$ are integers, and a hyper-rectangle $B=\bigwedge_i x_i\in[a_i, b_i]$ where $a_i, b_i$ are constant integers, ...
• 1,345
251 views

### NP Intermediate problems over Reals

While studying ${\bf NP}$ complete problems we have from Ladners' theorem - if ${\bf P}$ $\neq$ ${\bf NP}$-there are ${\bf NP}$ problems not in the class ${\bf P}$ nor ${\bf NP}$-complete. Ladners' ...
• 1,261
642 views

### Computation of reals: floating point vs TTE vs domain theory vs etc

Currently, computation of reals in most popular languages is still done via floating point operations. On the other hand, theories like type two effectivity (TTE) and domain theory have long promised ...
• 523
152 views

### Is the nonnegativeness of a polynomial hard for $\mathsf{NP}_\mathbb{R}$?

It is clear that the following problem is in $\mathsf{NP}_\mathbb{R}$. Input: a list $P$ of triplets $(a,s,t)$ where $s$ and $t$ are nonnegative integers. Output: is there an $x\in \mathbb{R}$ such ...
1 vote
237 views

### Is there any research on approximation of reals with computable numbers

I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
• 127
1 vote
120 views

### Computing log of sum of positive integers

As input, we are give $k$-bit approximation (after the decimal point) of $\log(a)$ and $\log(b)$ for positive integers $a$ and $b$, i.e, we are given $\alpha$ and $\beta$ (as binary strings) as input ...
• 727
409 views

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

As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals or the computation models over reals is not in ...
• 1,079
333 views

### Berman-Hartmanis Isomorphism for NP$_{\mathbb{R}}$?

Using the real-RAM/BSS model, we have the class NP$_{\mathbb{R}}$, (where a BSS is the Blum-Shub-Smale model of a computer with operations over reals). We have NP$_{\mathbb{R}}$ complete problems. ...
• 1,261
500 views

### The exponential function over algebraic numbers

Given an algebraic number $\alpha$, I am interested in finding an approximation of $\Re(e^\alpha)$ up to a given precision, where $\Re()$ refers to the real part of the complex number. Formally, I ...
• 181
1k views

### To what extent can the mathematics of Reals be applied to Computable Reals?

Is there a general theorem that would state, with proper sanitization, that most known results regarding the use of real numbers can actually be used when considering only computable reals? Or is ...
• 1,542
337 views

### What complexity issues are there in considering quantum algorithms with infinite gate-sets?

Short Version Suppose that you want to consider a model of quantum computation in which the gates used in the circuits may depend on the input size. Are there pitfalls to avoid when defining the ...
• 8,851
316 views

• 21
196 views

### Reference for the undefinability of modulus of continuity functional in PCF?

Can someone point me to the reference for the non-definability of the modulus of continuity functional in PCF? $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\bool}{\mathsf{bool}}$ Andrej Bauer has ...
• 32.7k
567 views

### Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)

I know the Blum-Shub-Smale model. It is claimed to provide a theoretical framework for algorithms in real and complex algebra and analysis. A very general question: Most algorithms compromise of ...
• 1,163
1 vote
172 views

### Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation?

Let's say I had an optimization problem $$\min_{x \in D} f(x)$$ Where $D \subset \mathbb{R}^n$ and $f:\space D \rightarrow \mathbb{R}$, and the minimum is said to exist. Imagine I had a ...
• 113
6k views

### Sum-of-square-roots-hard problems?

The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater ...
• 23.2k
1k views

### Complexity of computing shortest paths in the plane with polygonal obstacles

Suppose we are given several disjoint simple polygons in the plane, and two points $s$ and $t$ outside every polygon. The Euclidean shortest path problem is to compute the Euclidean shortest path ...
• 23.2k
5k views

### Time complexity of Bellman-Held-Karp algorithm for TSP, take 2

A recent question discussed the now-classical dynamic programming algorithm for TSP, due independently to Bellman and Held-Karp. The algorithm is universally reported to run in $O(2^n n^2)$ time. ...
• 23.2k
2k views

### Consequences of existence of a strongly polynomial algorithm for linear programming?

One of the holy grails of algorithm design is finding a strongly polynomial algorithm for linear programming, i.e., an algorithm whose runtime is bounded by a polynomial in the number of variables and ...
• 2,747
4k views

### What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?

Background The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore ...
• 21.7k
Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number Let Set $M=${$(c,k,m) |$ the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ is unbounded ...