# Tagged Questions

Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

255 views

### What's the most efficient algorithm for Divisibility?

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
556 views

### Is there a theory that combines category theory/abstract algebra and computational complexity?

Category theory and abstract algebra deal with the way functions can be combined with other functions. Complexity theory deals with how hard a function is to compute. It's weird to me that I haven't ...
192 views

### How to maximize the number of operations in process

In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word. If we are given an ordered ...
535 views

### Hardness of finding eigenvalues over finite fields

How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?) How ...
59 views

77 views

### The role of the extraction matrix in a Kalman filter

The extraction matrix shown as $H_k$ below, transforms the state vector into a form that can be subtracted from the measurements vector: $\hat{X}_k = \hat{X}_k^- + K_k ({z}_k - H_k \hat{X}_k^-)$ ...
92 views

34 views

### Why does the cutting plane method for integer programming run in exponential time?

I am looking for a proof of the fact that the cutting plane algorithm for integer programming does not run in polynomial time. The algorithm consists in adding constraints to the initial problem in ...
40 views

### Are binary bit-strings the most efficient representation of integers?

There is no format more popular in the world than the representation of Integers: 32-bit and 64-bit strings are used by basically every single computer in existence and there's no practical reason to ...
52 views

### Is it possible to reduce Theory of Rationals to Theory of Natural Numbers?

Is the following possible ? $$Th( \mathbb{Q}, +, \leq ) \leq^{\log}_m Th( \mathbb{N}, +, \leq )$$ I believe it is not possible since Natural Numbers are not dense. It is also not possible  Th( \...
82 views

### Fastest way to find linearly independent columns of a matrix

Given a rectangular matrix $X$ of size $n\times m$ with $m>n$, what is the fastest way to find the linearly independent coloums. Robust methods like SVD or RRQR decompostion have complexity of ...
82 views

### A question on GCT

In http://ramakrishnadas.cs.uchicago.edu/gctriemann.ps it is stated that there is an unknown non-standard riemann hypothesis. AFAIK riemann hypothesis in AG was shown using Etale cohomology by Artin, ...
104 views

### Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
48 views

70 views

### Could any one explain the difference between the theorems?

In the paper http://annals.math.princeton.edu/2007/165-2/p04 Theorem 2. Let $b \ge 2$ be an integer. The b-ary expansion of any irrational algebraic number cannot be generated by a finite automaton. ...
51 views

### Splitting a graph into two isomorphic parts

Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...