All Questions

11,649 questions
Filter by
Sorted by
Tagged with
16 views

Fairness property in transition system : Is there a formalization other than Linear Temporal Logic (LTL) or Temporal Logic of Actions? (TLA)

Is there a formalization other than Linear Temporal Logic (LTL) or Temporal Logic of Actions? (TLA)(1) For example, in this transition system, I want to express that the action d will be performed ...
28 views

Hamilton path in planar graphs

Is hamilton path problem NP-complete in planar graphs? If yes. In which paper can the proof be found? I think that properly colored hamilton path is also NP-complete in planar graphs, has it been ...
12 views

an introduction to bioinformatics algorithms solution manual pdf

I'm looking for exercise solutions for "An Introduction to Bioinformatics Algorithms" book. Can anyone help me and send it to me if they have it? The above book is written by the following ...
52 views

Is it known whether $FPT=EPTAS$?

I know that $EPTAS \subseteq FPT$. Is it known whether also $FPT \subseteq EPTAS$?
98 views

34 views

Show that PARITY has a uniform network of circuits of size O (n) [closed]

How can I show that PARITY has a uniform network of circuits of size O(n)?
51 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 ...
95 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 ...
288 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-...
88 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 ...
42 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 ...
30 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 ...
30 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 ...
156 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 ...
56 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 ...
34 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 ...
85 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 ...
101 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 ...
231 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...
49 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 ...
131 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 ...
59 views

37 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: ...
53 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 ...
76 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 ...
143 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 ...
85 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 ...
524 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.
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 ...