All Questions

Filter by
Sorted by
Tagged with
-2
votes
0answers
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 ...
-3
votes
0answers
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 ...
-5
votes
0answers
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 ...
-1
votes
0answers
52 views

Is it known whether $FPT=EPTAS$?

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

Satisfiability and a Galois Theory Analog

Let $v(a, b)$ be a binary predicate, and define $\phi$ as follows: $$\phi: v(a_1, b_1) \land v(a_1, b_2) \land (a_1, b_3)$$ where our universe consists of two sorts $A: \{a_1, a_2, a_3\}$ and $B: \{...
3
votes
0answers
29 views

Hardness of computing entropy of a function on uniform input distribution

Let $p \geq q \in \mathbb{N}_+$, and let $L_\mathsf{max-entropy} := \{(f,k) \in \{0,1\}^{\lambda^p} \times \{0,1\}^{\log\lambda} | \lambda \in \mathbb{N} \wedge \mathrm{H}(\underbrace{C_f(\mathcal{U}_{...
-3
votes
0answers
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)?
0
votes
0answers
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 ...
-1
votes
1answer
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 ...
6
votes
2answers
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-...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
-2
votes
0answers
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 ...
-1
votes
0answers
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....
-1
votes
0answers
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 ...
6
votes
2answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
6
votes
1answer
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 ...
5
votes
2answers
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 $...
1
vote
0answers
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 ...
2
votes
2answers
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 ...
0
votes
0answers
59 views

Name for words without squared symbols

Is there a common name in combinatorics for words that do not have square of size 1 ? That is words such that no symbols appears twice in a row or, more formally, words not in $\bigcup_{s\in\Sigma} \...
-2
votes
0answers
23 views

Min cost max flow with min vertex requirement

I have a bipartite graph with edge costs. For any vertex $v$ and an integer $l$, we want to know wether it is possible to have at least flow $l$ on every vertex $v$. (And if so the min cost). That is, ...
2
votes
0answers
30 views

Is logarithmic additive approximation to bin covering possible?

For the bin packing problem, the Karmarkar-Karp algorithm (1982) finds in polynomial time a packing with $OPT+O(\log^2(OPT))$ bins, and this was recently improved by Hoberg and Rothvoss (2017) to $OPT+...
-1
votes
0answers
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 ...
0
votes
0answers
59 views

Is there a term for 'no-turn-back walk' in graph theory?

Let $G$ be a finite undirected graph. A walk in $G$ is a finite sequence $<v_1,e_1,v_2,e_2,\dots,v_{k-1},e_{k-1},v_k>$ where $v_j$'s are vertices in $G$, $e_j$'s are edges in $G$, and $e_j=v_jv_{...
-1
votes
0answers
72 views

Expert Opinion on the Importance of Polynomial Hierarchy Collapse

$P\ vs\ NP$ and $NP\ vs\ co-NP$ are perhaps the two central questions in TCS and Complexity Theory with numerous surveys devoted to these problems. But (relatively) not much has been discussed ...
2
votes
0answers
71 views

Approximate (in hamming distance) subset representation

Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the ...
1
vote
0answers
35 views

Does high connectivity of line graph of $G$ imply high (cyclic) connectivity of $G$?

All graph considered here are finite, simple and undirected. We know that a graph $G$ is $k$-edge connected if and only if its line graph is $k$-connected (where $k\in\mathbb{N}$). In particular, if $...
0
votes
0answers
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: ...
-2
votes
0answers
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 ...
2
votes
0answers
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 ...
4
votes
1answer
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 ...
6
votes
1answer
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
-2
votes
0answers
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 ...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
8
votes
3answers
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 ...
6
votes
0answers
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 ...
3
votes
1answer
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 ...
3
votes
0answers
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 ...
2
votes
1answer
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$ ...
0
votes
0answers
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, ...
-1
votes
0answers
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.
4
votes
0answers
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 ...
2
votes
0answers
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 ...

15 30 50 per page
1
2 3 4 5
233