Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

1
vote
0answers
14 views
+50

calculating input size of extreme point for polyhedra

Conside the nonempty polyhedral set $F=\{x\in\mathbb{R}^n|Ax=b,x\ge > 0\}$, where $A\in\mathbb{Z}^{m\times n}$ and $b\in Z^m$ take integer values. Let $$a_1=\max_{ij}\{|a_{ij}|\}\hspace{0.1in} ...
17
votes
2answers
1k views

Is factoring polynomials as hard as factoring integers?

There seems to be a consensus that factorization of integers is hard (in some precise computational sense.) Is it known whether polynomial factorization is computationally easy or hard? One thing I ...
1
vote
1answer
31 views

Relation of encryption to P, NP, and NP-Complete

After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ...
0
votes
0answers
18 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
21 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
23 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
1answer
39 views

Properties of smallest expressions for polynomials, and potential proof.

See here for an intro. Smallest expressions for polynomials is analogous to smallest grammars for strings. Let $R = \Bbb{Z}_p[x_1, \dots, x_k]$. My goal is to prove that for any $\ \ h(k,p) = \max ...
0
votes
2answers
6 views

Linear search average-case complexity?

I am trying to find the average case complexity of the linear search. I know the answer is O(n), but is this correct: The first element has probability $1/n$ and requires 1 comparison; the second ...
2
votes
0answers
34 views

Is there any oracle A s.t. NP$^A$ $\neq$ EXP$^A$

I think the answer is yes because we do not know whether NP = EXP. But i couldn't find one.
1
vote
2answers
53 views

I want to know an estimate of $a_{i, j}$

Let $$ a_{ij} = \begin{cases} -1, & \text{if $i = -1$ and $j = -1$} \\ 1, & \text{if $i = -1$ and $j \ne -1$} \\ 1, & \text{if $i \ne -1$ and $j = -1$} \\ a_{i-1, j-1} + ...
0
votes
1answer
21 views

Are there known patterns among minimal expressions?

Let $R = F[z_1, z_2, \dots]$ be the finite-degree polynomials in a countable number of variables. Let $\mathcal{E}(R)$ be the set of all expressions of polynomials. Note that there could be an ...
1
vote
1answer
20 views

Computational complexity of expanding a MacLaurin/Taylor Series

What methods exist to computationally determine the first $k$ coefficients of a function (possibly polynomial or rational polynomial function)? How do Mathematica/MatLab/Maple/etc. solve this ...
1
vote
3answers
26 views

How do you reckon Big-O analysis with infinite problem sets?

Let $f : X \to Y$ be a problem, for instance, $f: \Bbb{Z} \to $ a factor. Given input measure $n = |x|$, then our problem is $O(g)$ if there exists an algorithm running on a standard machine, and an ...
0
votes
1answer
49 views

Existence of a det. poly-time algo for problem $f: X \to Y$.

$f : X \to Y$ is a deterministic polynomial-time algorithm for problem inputs $x \in X$ and problem outputs $f(x) = y \in Y \iff $there exists a polynomial $P_f \in \Bbb{Z}[x_1]$ such that $C\cdot ...
1
vote
0answers
66 views

Necessary and sufficient conditions for $\rm P \neq NP$ maybe?

Please review the $\rm P \neq NP$ problem here. I'm working on an algebraic approach to this problem, and all my notes are currently here. Conjecture 1 For all $f \in F[x_1, \dots, x_k]$, a minimal ...
0
votes
0answers
42 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 ...
1
vote
1answer
30 views

How do you define computational complexity abstractly?

Let the problem we're studying be $f : X \to Y$. Say, I don't know what I want to define time-complexity with respect to, I just know I have a map $|\cdot| : X \to \Bbb{R}$, such that $|\cdot| \geq ...
0
votes
1answer
52 views

Do there exist polynomials not computable in polynomial time?

Motivation: Computing a problem in $k$ memory slots Do there exist polynomials in $R = \Bbb{Z}_p[z_1, \dots, z_k]$ that can't be computed in time polynomial in $k,p$? Thanks... Good luck! Edit. I ...
0
votes
0answers
25 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
1answer
22 views

Any problem computable in $k$ memory slots can be computed with polynomials.

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, ...
2
votes
4answers
1k views

The tricky time complexity of the permutation generator

I ran into tricky issues in computing time complexity of the permutation generator algorithm, and had great difficulty convincing a friend (experienced in Theoretical CS) of the validity of my ...
-2
votes
1answer
24 views

travelling salesman problem approximation [closed]

Consider the symmetric travelling salesman problem $\Delta TSP$: An instance consists of a complete undirected graph $G$ (all possible edges are present), a nonnegative integer cost $c_{ij}=c_{ji}$ ...
0
votes
1answer
28 views

Is there a way to compute if(i < j) k := (a + b)c with polynomials over $\Bbb{Z}_p$?

Let $p$ be a prime and let all variables be in $\Bbb{Z}_p$. Then you can write the result of if(i > 0) k = (a + b)c; (C code) as a polynomial $k := ...
0
votes
1answer
20 views

circuits complexity

I ran into this claim and I dont really understand why it is true ( and I need to use it for proving other things) Every function from $(0, 1)^n$ to $(0, 1)$ is computable by a $2^n10n$-sized ...
0
votes
0answers
11 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, ...
2
votes
0answers
27 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
0
votes
1answer
218 views

Finding maximum of array consisting of an exponential amount of positive integers

Consider an array of an exponential amount of positive integer numbers, let's say $$ x_1, x_2, \ldots, x_{2^k} $$ for some fixed positive integer $k$. The question is the following. What is the ...
1
vote
0answers
27 views

Can cuts of size 2 be detected in linear time in an undirected, unweighted graph?

I'm having trouble finding any literature on the specific subject of 2-edge cut detection. It's not hard to come up with an algorithm that finds all 2-edge cuts in quadratic time, but it's not clear ...
1
vote
0answers
78 views

“Balancing” two infinities

Given these two computational complexities of 2 algorithms: $\exp(O(\sqrt{\log n \log \log n}))$ $O(\sqrt{\exp n} / \log{ \sqrt{ \exp n} })$ where I imagine the first one goes to infinity slower ...
3
votes
1answer
901 views

what is the computational complexity of solving a quadratic program with linear inequality constraints

I'm aware of several solution methods and have several solvers at my disposal, but I can't for the life of me find analysis on the complexity. In particular, I'm interested in the complexity of ...
1
vote
1answer
68 views

The complexity of counting solutions to $x_1 + \dots + x_m = N$ in non-negative integers under constraints

Consider the equation $$x_1 + \dots + x_m = N$$ where $x_1,\dots,x_m \ge 0$ and under the additional constraints $x_k \le a_k$ for $k=1,2,\dots,m$. I'm interested in knowing whether the number of ...
4
votes
2answers
235 views

Is there a function that only generates primes?

The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$? I'm having difficulty specifying exactly what I want "nice" to mean, ...
1
vote
2answers
107 views

List of calculation rules for asymptotic notation?

Background: I am working my way through CLR/CLRS's proof of the master theorem (section 4.4 in the 1st and 2nd editions of Introduction to Algorithms), and I'm doing my own write-up of this proof1 ...
0
votes
0answers
13 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
20 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 ...
2
votes
0answers
18 views

Complexity of finding extremal rays

Suppose that $\{L_i\}$ is a collection of $k$ linear forms on $\mathbf R^n$. Let $$C=\{x \in \mathbf R^n : L_i \cdot x \geq 0 \text { for all } i \}$$ be the closed convex cone defined by the ...
1
vote
0answers
44 views

If $P=NP$, prove that $L' \in NP$

I think I'm overthinking this problem and need some hints in the right direction. The goal of this question is to show that if $P=NP$ then for every language $L \in NP$ via a polynomial time verifier ...
0
votes
1answer
14 views

Order functions by speed of their asymptotic growths

We are given list of functions. Task is to sort it by the speed of their asumptotic growth in ascending order. Yes, it's a homework. I already spent some solid amount of time calculating limits. I ...
3
votes
1answer
108 views

Minimizing Height of a Table

This optimization question popped into my mind while working with latex tables: Suppose we have a table with $m$ rows and $n$ columns, and for each $1\le i\le m,1\le j\le n$ we are given $T(i,j)$ ...
0
votes
0answers
9 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
27 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
2answers
37 views

What does psuedo-polynomial algorithm for subset sum problem mean?

Help me out here - just trying to better understand what 'psuedo-polynomial' means... If the input to an NP-Complete problem is 100 items(ie n=100), and the 'target' is the actual value '100'(t=100): ...
7
votes
3answers
228 views

Which is easier to work out: determinant or inverse?

Suppose $A\in M_n(R)$ be a $n\times n$ matrix over some ring $R$. Which of the following two tasks is easier? to work out $\det(A)$; to work out $A^{-1}$. More specifically, I want to know the ...
2
votes
1answer
61 views

Prove 2-HamiltonianCycle $\in \textbf{NP}$

Just want to verify that I have the right idea here with this hamiltonian cycle question. $HC$ = $\{\langle G \rangle$ | $G=(V,E)$ is an undirected graph such that there is a simple cycle (no vertex ...
1
vote
0answers
38 views

Is $\log^* (n+1)^{n+2} \in O(\log^* n)$?

I would like to know if $\log^* (n+1)^{n+2} \in O(\log^* n)$, where $\log^*$ is the iterated logarithm. I tried doing: $ \log^* (n+1)^{n+2} =\\ \log^{*}(\log(n+1)^{n+2})-1 =\\ \log^{*}((n+2) \cdot ...
1
vote
2answers
57 views

Implication of P =NP on video games?

I was wondering if NP problems were actually solvable in P time, then what will be the impact on Video Games, if any ?
3
votes
0answers
27 views

Examples of functions which grow faster than their computational complexity.

A good example of this would be the function $f$ defined as follows, $f(n) = (10^n-1)$. While in this form it's equation is exponential, it is easy to note that $$f(n) = 99...9 \,(n \text{ times}).$$ ...
1
vote
1answer
31 views

Decidability of normal modal logics

Let's say we have systems of modal logic defined as smallest sets containing propositional tautologies, all instances of schema $\square F \to (\square(F \to G) \to \square G)$ all instances of ...
1
vote
2answers
16 views

exponential time complexity

given that: $f(n) = a^n$ and $g(n) = b^n$ where, a,b are positive integers and n is a positive real number does there exist some $f(n) \notin \mathcal{O}g(n)$? ie. $f(n) \leq c_1 \cdot g(n)$ is ...
2
votes
0answers
15 views

A confusion about RP class of problems

I have some notes which introduces the quantifier $\exists^+x$ and interprets it as "the overwhelming majority of $x$". Then, it defines RP (Randomized Polynomial) as: $$ L\in RP\Leftrightarrow ...