# Tagged Questions

Questions related to the (computational) complexity of solving problems

23 views

### What is the relation between Universality and simulations of Cellular Automata structures?

Elementary Cellular Automata and Conway's Game of Life show interesting Cellular structures, suppose we have a computational model {a Cellular Auotmaton} that can simulate both CA types (ECA & ...
79 views

### Variant of (WEAK) PARTITION with 2 distinct solutions

I am interested in the complexity of the following problem: Input: A list $a_1\leq ⋯ \leq a_n$ of positive integers. Question: Are there two vectors $x, x'\in\{−1,0,1\}^n$, with at least one $x_i$ ...
104 views

### Simpler proof of Rabin's Compression Theorem?

I was doing a presentation on Rabin's Compression Theorem, when someone in the audience brought up a point I have no answer to. Rabin's Compression Theorem states that every reasonable complexity ...
90 views

### What is the time complexity of checking if a number is prime?

Could some one please explain how to get the time complexity of checking if a number is prime? Im really confused as to if its O(sqrt(n)) or O(n^2). I iterate from i=2 to sqrt(n) and continuously ...
37 views

### Complexity of calculating average across distributed network?

What is the communication complexity of the best known algorithm for computing the average of a set of N*D numbers distributed across N nodes with D values per node? Assume you have full control over ...
133 views

### Complexity for finding a ball that maximizes the number of points lying in it

Given a set of points $x_1, \ldots, x_n \in \mathbb{R}^2$ and a radius $r$. Which is the complexity of finding the point with higher number of points at a distance smaller than $r$. E.g the one that ...
53 views

### Proving NP-Completeness by reduction

I'm given a more restricted version of 3-SAT called 3-SAT-M: Problem: 3-SAT-M INPUT: A set of clauses C {c1,...,ck} over n boolean variables {x1,...,xn}, where every clause contains ...
78 views

### Is sierpenski's triangle considered to be a computational model?

I was reading about sierpenski's triangle and i found that it is similar to pascal's Triangle, which can show coefficients in binomial expansion, also rule 90 from ECA. If Sierpenski's triangle can ...
57 views

### Kolmogorov complexity of strings in a given language

Consider the language $$L = \{1^i 0^j 1^k \mid i + j = 2k, k ≥ 1\}\,,$$ and let $x_n$ be the canonical $n$'th word in $L$. My problem involves proving that the Kolmogorov complexity of $x_n$ can be ...
11 views

### Computational complexity of emulating (untyped) λ-calculus with a queue machine

I am looking for bounds - both lower and upper - on the time, spacial, and state/symbol (i.e. number of states and symbols required) complexity of simulating the (untyped) λ-calculus with a queue ...
16 views

### Complexity bounds for Turing equivalence [closed]

I am looking for bounds - both lower and upper - on the time and spacial complexity of simulating Turing-complete systems with each other. (I am aware that both time and space are ill-defined with ...
22 views

### What is the relation between Universality and Geometric shapes in cellular automata?

When wolfram described Elementary Cellular Automata, most of the rules appeared as triangle and lines. Now, Rule 110 consists of triangles which is proved to be universal. Is there a relation ...
619 views

### If P=NP, then is L=NL?

If P=NP, then is L=NL? I am asking this question, because for other non-deterministic classes, it seems that P=NP establishes that they are equal to deterministic counterparts.
67 views

### NP-hardness of a scheduling problem

Problem: Given an undirected, weighted, complete graph $G = (V, E, w, c)$. $w$ is the time weight function on edges, $w:E \to \mathbb{N}^{+}$; $w(e)$ represents the time it takes to travel along edge ...
24 views

### “Archiving” byte sequence into human-readable set of chars

Ok, lets assume we have sequence of 1000 bytes. So the possible number of value variations is 2^100. Is there a way to "index" each variation with letters and decimal numbers (A-Z, 0-9), having as ...
35 views

### ZK proof that I possess a ZK proof for membership in $L$?

A zero-knowledge proof system for a language $L$ is an interactive proof system where a prover $P$ (a Turing machine) tries to convince a verifier $V$ (a polynomially bounded Turing machine) in a ...
30 views

### Is it possible to reduce functional equations to SAT?

The problem of finding a solution for functional equations can be defined as: Let A0, A1, A2... An, B0, B1, B2... Bn, X be terms of the lambda calculus, all terms known, except for X, unknown. ...
40 views

### Why is the probability used in the definition of RP complexity classes, arbitrary?

I was looking at the following wikipedia article on the RP complexity class: https://en.wikipedia.org/wiki/RP_(complexity) In it's definition it states: If the correct answer is NO then it always ...
43 views

### Convex Hull in no particular order

The proof for the $\Omega(n\log n)$ lower bound for calculating the convex hull by using order-type predicates that I have come across uses the fact that if there was possible to calculate the convex ...
32 views

### Can a cellular automata structure simulates another cellular automata structure?

In Elementary Cellular Automata, rules can show one pattern, but i am wondering if there is something where a cellular automata structure can simulate another structure? Is there a category for this ...
70 views

### difference between complexity and computability theory?

what is the difference between complexity and computability theory? Is there any overlap between the two or are they completely different? or is one a subset of the other?
35 views

### For tiling simply connected regions with shapes beyond just rectangles, is there a lower # of tile shapes needed for NP-completeness?

In "TILING SIMPLY CONNECTED REGIONS WITH RECTANGLES" by Igor Pak and Jed Yang, they show there is a set of "no more than $10^6$ rectangles" such that the problem of tiling an arbitrary simply ...
42 views

### Monotone formulas versus Monotone Circuits [closed]

Are monotone formulas (formulas using positive constants, additions and multiplications) more powerful than monotone circuits? Are there illustrative examples?
24 views

### Meaning of ⟨_⟩ in the context of verifiers

A verifier for a language A is an algorithm V, where $$A = \{w \mid V \text{ accepts \langle w,c \rangle for some string c}\}$$ ($c$ is called a certificate or proof) What's the definition ...
83 views

### Why is $P \subseteq NP$?

The Clay paper gives a short proof on this in page 2: http://www.claymath.org/sites/default/files/pvsnp.pdf However, Where does it come from that these are inclusive sets and not separate? Or that ...
160 views

### What is the evidence that P could equal NP?

What is the evidence that P could equal NP? I guess this is the same as asking: If it's known that $P \subseteq NP$ (depending on standard), then why is this not enough? Why assume that P could ...
47 views

### Do poly-time algorithms exist whose time complexity is unprovable?

If not, is there a decision procedure that successfully classifies any polynomial time algorithm as poly-time within a time polynomially bounded by the length of the input algorithm?
52 views

### What is the complexity of finding a regular expression equivalent to a given DFA?

I had taken a course long ago on complexity theory. I only remember basic things, so I am reading "Introduction to the Theory of Computation by Michael Sipser". The book in its first chapter ...
34 views

### Show that $L^c$ is also in NP

Let L be a language over Σ i.e., $L\subseteq Σ^∗$. Suppose L satisfies the > two conditions given below. L is in NP and for every n, there is exactly one string of length n that belongs ...
904 views

### How much complexity difference can there be between finding a solution to a Sudoku puzzle and PROVING that the solution is the unique solution?

So usually Sudoku is $9 \times 9$, but this question extends to $n^2 \times n^2$ puzzles with $n > 3$ as well. There are many polynomial time deduction rules that can make progress in finding a ...
65 views

### Can any PEG grammar be parsed in linear time?

On the Wikipedia for PEG it is claimed: Any PEG can be parsed in linear time by using a packrat parser, as described above. However, packrat parsers can't handle left recursion. You can ...