# All Questions

11,646 questions
Filter by
Sorted by
Tagged with
17 views

20 views

### Show that PARITY has a uniform network of circuits of size O (n)

How can I show that PARITY has a uniform network of circuits of size O(n)?
23 views

### Lattice in computer science

What are the applications of lattice structure in cs? How important it is to learn lattice structure?
20 views

### SAT to k-in-3-SAT reduction

Given a 3-SAT clause. Is there a way to convert 3-SAT to k-in-3-SAT such that: The number of new variables introduced are less than the number of clauses (without adding dummy clauses etc.)? The ...
72 views

### Polynomially solvable 3-SAT problem instances

Given the 3-SAT problem with $v$ variables and $c$ clauses: Is there a clause to variable ratio for which the 3SAT problem is 'easy' i.e. solvable in polynomial time? We are assuming the 3-SAT ...
214 views

### Induction-recursion in models other than $\mathbf{Set}$

It is well-known that various flavors of induction-recursion are consistent*. Typically, this is proven by showing that the standard model of type theory in sets can be extended to include induction-...
86 views

### Why can't opaque optics form a category?

The optics Haskell package is an alternative to the famous lens package. lens uses a van ...
41 views

### Evaluating multidimensional polynomials

Are there efficient algorithms to construct optimal evaluators of multivariable polynomials? Here, an 'evaluator' can be thought of as an algorithm or description of how to evaluate a specific ...
29 views

### Searching for a proper example to get an better intuition for decidability

Let A be a nonempty alphabet, X ⊆ A∗ a decidable set, and Y ⊆ A∗ be a semi-decidable set. We assume that Y ⊆ X and that X \Y ⊆ A∗ is semi-decidable. Show that then the set Y ⊆ A∗ is decidable. I am ...
27 views

### Design a Turing Machine that calculates $f(n,m)= \lceil(n+m)/2\rceil$ [closed]

I am pretty new on computer theory and I'm trying to understand turing machines. The $\lceil\,\rceil$ means ceiling/the next integer above the result (for example, if the real result of division is 3....
18 views

### Finding a game where the set of Correlated equilibria is different from the set of Coarse correlated equilibria

For the recent exercise of my Game Theory lecture I am asked to find a game where the set of Correlated equilibria (CE) is not equal to the set of Coarse Correlated equilibria (CCE). Because we know ...
142 views

### Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?

For a non-empty $3-SAT$ with $n\geq3$ variables and $T\geq1$ non-identical non-degenerate clauses $C_i$: $$S=C_1 \wedge \ldots \wedge C_T$$ where a non-degenerate clause is one containing $3$ unique ...
54 views

### How can we prove what the shortest line between two points avoiding convex obstacles is? (visibility graphs)?

I came across the observation in russell & norvig's artificial intelligence book that the shortest path between two points while avoiding convex polygonal obstacles is a sequence of line segments ...
33 views

### Weak simulation of Clifford circuits

Quantum circuits composed by Clifford gates can be simulated by classical computation in polynomial time. More precisely, this simulation should be a weak simulation, i.e. it is possible to sample the ...
75 views

### Defining functions on non-inductive types using LEM in Coq

I'm trying to prove statements about homomorphisms in Coq. Specifically, about in which cases the existence of some set of homomorphisms implies the existence of a specific other homomorphism. I'm ...
74 views

### Is there a simplex-like algorithm that can be used with a separation oracle?

Linear programs can be solved in polynomial time using the ellipsoid method, but in practice the Simplex method is much more efficient, and the smoothed analysis framework of Spielman and Teng ...
203 views

### Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?

I am wondering about the following property $\text{(P)}$ of an $NP$-complete language $L$ \begin{align}\exists M\text{ a polytime machine}\lim_{n\to\infty}P(\text{M solves a random instance of size...
48 views

### Partition of multisets of polynomials

Problem: Given a multiset S of irreducible polynomials in Z[x], say YES if S can be partitioned into two nonempty multisets A and B such that both the product of all the elements of A and the product ...
125 views

### Separating 2-SAT from Clique

Since the P vs. NP problem is still an open problem, 2-SAT and Clique might both be in P if P = NP. Is there any known complexity measure whatsoever that is already mathematically proven to ...
58 views

36 views

### Can equations be used to transmit large amounts of information instead of directly sending it? [closed]

Can equations be used to send large amounts of information rather than sending the information itself you send an equation that when solved reveals the information? So rather than downloading billions ...
59 views

32 views

### Is having a particular form equivalent to being computable for functions on Church numerals?

In SKI-combinator calculus, consider the following function which reduces an expression (involving SKI and variables) to a canonical form: ...
50 views

### Polynomial time delay and Amortized analysis [closed]

In order to estimate the complexity of output sensitive algorithm, we usually use Polynomial time delay or Amortized analysis. In particular, an enumeration algorithm $A$ runs in polynomial amortized ...
80 views

### Online *detailed* tutorials about Komogorov Complexity

I'm a private math tutor who also tutors some theoretical CS. Last semester I had a student who needed tutoring in Kolmogorov Complexity. I told her that I only know about Kolmogorov Complexity, but ...
75 views

### Comparative communication complexity?

I was reading the book "Communication Complexity" by Kuschilevitz and Nisan and in Exercise 1.18 they introduce a variant of the normal vanilla 2-person deterministic communication ...
142 views

### Reference for automatically deriving dynamic programming algorithms from recursive algorithms?

This is what I'm looking for. Take a recursive algorithm: def fib(n): if n == 0 or n == 1: return n else: return fib(n-1) + fib(n-2) and turn it into ...
35 views

### Is the following special case of multiway number partitioning NP-hard?

The following problem is a decision problem of multiway number partitioning (wikipedia) (Note that $k$ is also a part of an input in the following problem, while $k$ is a fixed number in wikipedia ...
83 views

### Circuit uniformities more restrictive than $DLOGTIME$

$DLOGTIME$-uniformity was introduced by Barrington et al. here, and seems to be the standard lowest uniformity measure used for e.g. constant-depth circuit classes ($AC^0$, $ACC^0$, etc.). Are there ...
37 views

### Is it possible to find closest number to a given irrational one, which is obtained by dividing 2 numbers in a given range faster than O(n^2)?

Let's say I have a range from 11 to 99 I need to find: abs(a/b)-k = min, a nd b - integer, k-an irrational number I can just look at all pairs of numbers in ...
37 views

### What type of Problems (Class and types) Can Be Solved Effectively with Quantum Computers?

The Question: I'm trying to understand the type of problems that Quantum Computers are/will be good at solving and if there is a special class to categorizes these types of problems (e.g. Do we ...
56 views

### Summing over weighted paths optimally

Given an edge-weighted directed graph, how do you sum over all weighted paths between A and B while using the smallest number of multiplications? Is there a name for this problem? This comes up in ...
515 views

### What's the logical counterpart to jumps with arguments on CPS terms?

It's well known that the CPS (continuation-passing style) translation often employed in compilers corresponds to double negation translation under the Curry-Howard isomorphism. Though often the target ...
89 views

### For which type systems have normalizaton proofs been formalized?

I am trying to understand what the open problems are in the area of formalizing proofs of normalization for type systems. Obviously STLC has been done many times. For predicative System F, I found one ...
146 views

### Proof and interpretation of the No Free Lunch theorem in data privacy

This question relates to a supposed counterexample to the No Free Lunch theorem governing data privacy mechanisms, as stated by Kifer et al (Section 2.1). Colloquially, the theorem states that no ...
55 views

### Expressive power of lambda-calculus with restricted application

Consider a syntactic restriction of the (untyped) $\lambda$-calculus in which an application cannot have another application as an immediate subterm. More precisely, restricted terms ($R,S,...$) and ...
70 views

### On cubic planar graphs with face boundaries of length divisible by 4

All graphs considered here are finite, simple and undirected. Let $\mathscr{G}$ denote the class of cubic plane graphs for which all face boundaries are of length divisible by four. The 3-cube $Q_3$ ...
77 views

### Computational complexity of Private Computation

In a recent work (Sun2017), Sun and Jafar defined the Private Computation (PC) problem where a user wants to compute a function of $K$ datasets, using $N$ distributed and non-colluding servers, ...
34 views

### Semantics of assert b before S - Nielsen and Nielsen Exercise 3.2

I was wondering how to express this statement in natural and structural operational semantics. Further, how would we define the statement 'assert b' only.
113 views

### Split a string of positive numbers into substrings with decreasing totals

Suppose we're given a string of $n$ positive numbers and asked to split it into the maximum number of substrings whose totals are decreasing. I have an $O(n)$ time DP algorithm, but is it already ...
86 views

### Subtle part of seeing $C(F) \geq \chi(f)$

This question is certainly below research level, however I figured I would get the best answer here. I just started learning about computational complexity (from Arora and Barak) and I have a ...
41 views

### Which is more expensive, structural or nominal type-checking?

A type system is nominal when types can be given new names, and those new names are attached to new behaviors. To me, type-checking programs in a nominal type system seems like it must be no less work ...
I'm writing a paper in which I designed an algorithm running in $O(n^2m)\cdot T(f)$ to solve my problem, where $n,m$ is the size of input and $f:\mathbb{R}\rightarrow \mathbb{R}$ is a function, and \$T(...