Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

0
votes
0answers
16 views

$P=NP \Rightarrow P(S)=NP(S)$?

If $P=NP$, then is it possible to conclude that for every sparse set $S$, $P(S)=NP(S)$? ($P(S)$ means a class of sets for which a Polynomial Deterministic Turing Decider with Oracle Set $S$ exists, ...
0
votes
0answers
27 views

Hardness of bounded modular square root of 1

If we know any square root of 1 modulo N different from 1 and N-1, then we can find a nontrivial factor of N. So to find such a square root has a certain hardness. In fact, if in general we ask to ...
0
votes
0answers
19 views

computational complexity of $\sum_{k=1}^K {n\choose k}$

I would like to know what is the computational complexity of $n\choose k$ and $\sum_{k=1}^K {n\choose k}$ in terms of $\mathcal{O}$.
0
votes
0answers
37 views

Recursive Set and Complement Problem

if we have $$A=\{x:|W_x\ne\phi\}$$ can we say always my tight listed below is true? $A$ is recursive , $A$ is r.e, complement of $A$ is r.e, complement of $A$ is not recursive?
0
votes
0answers
32 views

L={(M,W) | M is a Turing Machine that stops on input W } is not R. E.

I've been thinking about how to show this but I'm stuck. on Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science (Computer Science and Scientific ...
0
votes
0answers
10 views

Polynomial-time reduction and complexcity sets P and NP.

hello I am having difficulties to understand the topic of P,NP and Polynomial-time reduction. I have tried to search it on web and ask some of my friends , but i havent got any good answer . I wish ...
0
votes
0answers
25 views

Using the pumping lemma to prove that a certain language is not regular

I've been trying to understand the pumping lemma since forever, I just don't know what it does, I have no clue what any of it does. My college professor sucks, he thinks writing a bunch of stuff on a ...
0
votes
0answers
22 views

Complexity of and an algorithm for finding ideals of a ring?

One of the problems that has been a roadblock in my understanding of ideals has been how one would find them. One way of finding an I of some ring R would be to say $ \forall x \in I, \forall r \in R ...
0
votes
0answers
47 views

Calculating time complexity of algorithms written in pseudocode.

Nowadays we are interested to find some algorithms with a prescribed running time. For example if for certain decisional problem $X$ there is an algorithm with running time $O(n^3)$ we try to break ...
0
votes
0answers
34 views

Is there a fast algorithm for computing the $(2^n)+1$ th last digit of $3^{2^n}$ in base $2$?

Is there an algorithm such that for some polynomial p, it always computes the $(2^n)+1$ th last digit of $3^{2^n}$ in base $2$ in at most p(n) steps for all nonnegative integers n? I'm only asking if ...
0
votes
0answers
43 views

Master Theorem and Logarithms

I am really struggling to understand the Master Theorem when in a formula: T(n) = aT(n/2) + f(n) f(n) takes the form of log(n), nlog(n) or nlog^k(k) For ...
0
votes
0answers
16 views

Deterministic polynomial algorithm for 7/8 of 3 CNF

Let I have 3 CNF with all $k$ terms having 3 different variables. I need polynomial time algorithm to set true or false for all variables so that at least $\frac{7k}{8}$ of terms are true. I know ...
0
votes
0answers
26 views

Algorithmic Complexity of Linear Independence

Given n m-dimensional vectors. You can determine linear independence by Gaussian elimination. http://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency Checking linear independence ...
0
votes
0answers
27 views

complexity of feasibility checking for a convex optimization problem

I just want to check with you all whether I understand it correctly or not. If I have a convex optimization problem like \begin{align} &\min \quad f(x) \\ & s.t. \quad h(x)≤0, \end{align} and ...
0
votes
0answers
10 views

Explanation of the complexity of sum of sum of sum …

What is the time complexity of the following equation? assuming each variable is K-ary? I think it is $K^2 + K^3 + K^3 + K^3 + K^4 + K^3 + K^2 = O(K^4) $ because the inner most sum has two ...
0
votes
0answers
20 views

Show L1 is in P, given that L2 is in P and L1 <=p L2

Given L1 and L2 are languages over alphabet Z. Also given that L1 <=p (polynomial time computable) L2 and L2 in P. What is the best way to show that L1 is in P (through definitions of class P and ...
0
votes
0answers
23 views

Basic questions about descriptive complexity

I'm trying to learn descriptive complexity, and I'm having trouble on a basic level wrapping my head around what it means for a logical formula to define a computational language. I've tried and ...
0
votes
0answers
26 views

How to prove this polynomial expression.

Let the polynomial be in $f$ be a map from $\Bbb{Z}_2^k \to \Bbb{Z}_2$, defined by $f = 1 + \sum_{i=1}^k x_i + \sum_{i\neq j; i,j = 1}^k x_i x_j + \dots + x_1 x_2 \cdots x_k$ Then I want to show ...
0
votes
0answers
45 views

My notes on $\Bbb{Z}/p\Bbb{Z}$-theoretic computational complexity

(Question at the very bottom) Def 1. Let $F = \Bbb{Z}_p$ be a finite field. Then an $F^k$-machine is a machine with $k$ input / output memory slots. All computations are done in the field $F$ and ...
0
votes
0answers
26 views

Not every polynomial in $\Bbb{Z}_p[x]$ can be factored, but can you do next best?

If $f \in R = \Bbb{Z}_p[x]$ is irreducible or doesn't have many factors then it could be hard to compute? Possibly, I'm not saying, but... any way, what if $f = h - g$ where $h, g$ are heavily ...
0
votes
0answers
13 views

Are these computational models equivalent?

Let $f : X \to Y$ be a problem that you want to compute. Say we have an $O(1)$-computable maps, $\phi, \psi$, such that $X \xrightarrow{\phi} (\Bbb{Z}_n)^k \xrightarrow{\psi} Y$. After all, ...
0
votes
0answers
15 views

How to determine sub-exponential time growth?

I'm a little bit confused of sub-exponential time growth; consider the definition from Hoffstein's book An Introduction to Mathematical Cryptography: Given input of $k$ bits, then if an algorithm ...
0
votes
0answers
31 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
0
votes
0answers
11 views

Proof of theorem about connection between nondeterministic and deterministic Turing machines complexity classes

I need source for proof of this theorem: Every $T(n)$ time nondeterministic Turing machine has an equivalent $2^{O(T(n))}$ deterministic Turing machine. I have book by Michel Sipser, ...
0
votes
0answers
28 views

Prove that THEOREMS is NP-complete

I have an essay where I shall explain polynomial time reductions, NP definitions and give an "non-strict" proof that THEOREMS is NP-complete. THEOREMS is the problem of providing mathematical proofs ...
0
votes
0answers
80 views

Prove that div(x,y) is primitive recursive (integer division

Prove that div(x,y) is primitive recursive (integer division). I tried thinking about it, I just don't know how to write it formally. it is kinda obvious that I should subtract y from x several times ...
0
votes
0answers
26 views

Why $17T(n/16) + n \log n$ satisfies the case 2 of the Master Theorem?

Using the Master Theorem, we have that $17T(n/16) + n \log n$ is $\theta(n^{log_{16}17} log^2 n)$ My question is, why $n \log n = \theta(n^{\log_{16}17} \log^1 n)$, being $\log_{16}17$ approximately ...
0
votes
0answers
12 views

Complexity Multiplication Matrix-Vector in binary

I'm calculating the complexity of certain algorithm and I need know What's the complexity of the best algorithm, without parallel, to calculate the matrix vector multiplication over GF(2)?. The ...
0
votes
0answers
44 views

How to convert a subgraph isomorphism problem to subset sum problem

Let's say you want to solve a subgraph isomorphism problem using a subset sum solver. What would be the right steps to convert SGI to SS?
0
votes
0answers
43 views

What is the complexity of computing some problems related to real analysis

I was thinking. I do not know whether my question has any sense. I want to know is there any way to compute analytically or explicitly some of the problems give below. What is the complexity of ...
0
votes
0answers
32 views

What is the space complexity of inverting a real valued sparse banded diagonal symmetric matrix?

Of course, when I say ``inverse'' what I really mean is solving a system of equations $Ax=b$ where $A$ is sparse, banded diagonal, symmetric, real valued $N \times N$ with a bandwidth of $k$. I know ...
0
votes
0answers
14 views

In the definition of NP, is it required to have polynomially bounded length of certificate?

So given the definition in our lectures, we were told that NP is defined as the set of languages $L$ s.t. there exist a polynomial time bounded Turing-acceptor M s.t. $L ={w: M accepts(w#c) for some ...
0
votes
0answers
46 views

Prove that $EXP^{EXP}\neq EXP$

I have to prove that $EXP^{EXP}\neq EXP$. $$EXP=EXPTIME$$ $EXP^{EXP}$ is all the languages which can be solved by turing machine with oracle calls (which solves language in $EXP$) in $EXP$ time. I've ...
0
votes
0answers
13 views

What are the current lower bounds for $NTIME$ vs $DTIME$?

Trivially, we have $DTIME(f(n)) \subset NTIME(f(n))$. Is it known whether or not this inclusion is strict? Do we know if $DTIME(f^c(n)) \subset NTIME(f(n))$ for any $c$? Is there any $c$ for which ...
0
votes
0answers
16 views

Any problems that reduces to shortest path?

I am writing an introduction to complexity theory, and in my first chapter I discuss polynomial-time algorithms with language theory and shortest path as an example problem. My professor wanted me to ...
0
votes
0answers
27 views

Why is integer programming in fixed dimension easier than in general?

When the dimension is an a priori fixed constant, then integer programming feasibility (the existence of an integer point in a polyhedron) can be decided in polynomial time. If the dimension is not ...
0
votes
0answers
20 views

Complexity of Cartesian product involving multiple set

I want to evaluate complexity of Cartesian Product involving N sets, each of N set as subset of super set having 2E elements ( actually E distinct elements, each repeated twice ), Repetition of ...
0
votes
0answers
17 views

Reduction of halting problem

I can show that this reduction !H ≤ H where H is the general halting problem an !H is the complement of it. But what with H ≤ !H ...
0
votes
0answers
12 views

Where are PPAD problems located?

I'd like to produce a figure like this one and I'd like to add the PPAD class and the PPAD-complete class. I know that those classes are somewhere inside NP-complete set, is this right? Could ...
0
votes
0answers
21 views

complexity of an optimization problem

Consider $n$ variables $x_1, \cdots, x_n$ with the constraint $\sum_{i=1}^n x_i=1$ and $x_i\geq 0$. I want to minimize $\vec{a}^T (I-\alpha A(\vec{x}))^{-1} \vec{b}$, where $\vec{a}$ and ...
0
votes
0answers
47 views

How can I find the distribution of a recursive relation with two parameters?

Suppose we have a recursive relation, e.g. $G(n,m) = G(n-1,m) + G(n, m-1)$, with some initial points where $n,m \in \mathbb{Z}^{+}$ and $F$ is a finite-field, e.g. $\mathbb{Z}_p$ for a prime $p$. Also ...
0
votes
0answers
29 views

any approximation for $\sum_{i_3=3}^{n-k+3}\sum_{i_4=i_3+1}^{n-k+4}\sum_{i_5=i_4+1}^{n-k+5}\cdots\sum_{i_k=i_{k-1}+1}^{n} 1, (n \gg k)$?

Is there any approximation for $$\sum\limits_{i_3=3}^{n-k+3}\sum\limits_{i_4=i_3+1}^{n-k+4}\sum\limits_{i_5=i_4+1}^{n-k+5}\cdots\sum\limits_{i_k=i_{k-1}+1}^{n} 1, \quad (n \gg k)$$ ? We know that ...
0
votes
0answers
41 views

Quanitified boolean formula and equality of P=NP

This is an exercise problem in "Computational complexity: A modern approach" Let Σ2 SAT denote the following decision problem: given a quantified formula ψ of the form ψ = ∃x∈{0,1}n ∀y∈{0,1}m s.t. ...
0
votes
0answers
18 views

Reducing the complexity of a Combinatoric Equation

Given the equation: $$ P = \sum\limits_{n=1}^{\lfloor {\frac{q}{2}} \rfloor} {\dbinom{2n-1}{\frac{W}{2t}+n-1}\frac{1}{2^{2n-1}}} $$ Are there any algebraic tricks (or any others for that matter) ...
0
votes
0answers
27 views

Matrix scaling problem for Unitary matrices

I would like to know about the complexity of the following problem. Given a ($n\times n$) unitary matrix U and two row-vectors R and C of rational numbers, all of which less than 1, with ...
0
votes
0answers
101 views

Dynamic programming algorithm for GCD?

I can't seem to find a clear answer on this. I'm inclined to believe that there is not a DP solution for GCD, given the lack of information so far in my searches on the subject. I suppose that in ...
0
votes
0answers
25 views

Analysis of the successive elimination algorithm for multi-armed bandits

I'm referring to page 7 (page 11 if you look at printed page numbers) of http://moodle.technion.ac.il/pluginfile.php/328871/mod_resource/content/1/Chapter1_bandits.pdf Here's what he claims, and I'm ...
0
votes
0answers
7 views

Determining if a Language is contained in P, based on two representations of max runtime

Is the language L1 = {(M, w, 1^t) | M accepts w after running for max t steps} contained in the class P? I know that there are 2 main goals: runs in polynomial ...
0
votes
0answers
9 views

Polytime integral approximations in $n$ variables

Let $A = [0, 1]^n$ ($n \approx 16$ for my purposes). I have a function $f$, and I can query $f(x)$ in constant time. I want to computationally approximate $\int_A f(x)$. The natural solution is the ...
0
votes
0answers
275 views

Exact inversion of matrix complexity (by Gaussian elimination)

I would like to check if what I have done is correct. Please, any input is appreciated. Problem statement: Consider a non-singular matrix $A_{nxn}$. Construct an algorithm using Gaussian elimination ...