# All Questions

10,925 questions
Filter by
Sorted by
Tagged with
24 views

### How does complexity of a counting problem influence wether it admits a closed form formula or not?

In https://arxiv.org/abs/1412.1505, the section "Results on Data Complexity" mentions the fact that since the authors are about to proove $\#P_1$ complexity for weighted model counting in ...
43 views

### Fine-grained hardness results on exact computation of matrix multiplication output size

Consider two boolean matrices of dimension $\sqrt{N} \times \sqrt{N}$ with total $O(N)$ non-zero entries. Let $|OUT|$ denote the number of non-zero entries in the product of the two matrices. Is it ...
23 views

### Remove cycles from a stochastic comparison matrix, while doing the least amount of editing

Let $\mathcal P_n$ be the collection of all matrices $M \in [0, 1]^{n \times n}$ such that $M_{ij} + M_{ji} = 1$ for all $i, j \in [n]$. Such matrices are called comparison matrices. A comparison ...
12 views

### Examples of random deployment in wireless sensors networks

I have been doing some research and have found a lot of papers on the subject of random deployment in wireless sensor networks, but I haven't found a single example of its usage. Has it been used ...
85 views

### What graphs on $\mathbb{N}$ can be encoded as regular languages?

Suppose I represent the natural number 0 by "x", and use the symbol "s" for successor so that I get the following encoding of $\alpha : \mathbb{N} \rightarrow V$ of natural numbers ...
43 views

### Unambiguous Problems and Classes over Reals

Are there unambiguous analogues of $NP_{R}$ (using the BSS model, in all discussion)complete problems, and any results known about them? For instance, the canonical $NP_{R}$ complete problem $4FEAS$ (...
19 views

### Decidability of regular partition construction given its existence

Let $G = (N,T,P,S)$ be a context-free grammar where $T,N$ are sets of terminals and nonterminals respectively, $P$ contains all the productions of the grammar, and $S \in N$. If we know that $G$ is LL(...
60 views

### Functional abbreviation for Inst expression in Turing's 1936 paper

In Turing's 1936 paper "On Computable Numbers", For a Turing Machine $M$, $Inst(q_i S_j S_k L q_l )$ means that if $M$ scans symbol $S_j$ under $m-configuration$: $q_i$, then symbol on ...
81 views
+50

### How to calculate complexity in a high dimensional space?

Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong. For a specific f(), I'm defining a term '...
14 views

### Prove Polynomial Runtime of a 3-coloring Optimization Problem

Suppose we are given a graph $G$, and we want to color each node with one of three colors, even if we aren’t necessarily able to give different colors to every pair of adjacent nodes. Rather, we say ...
24 views

### Nominal Tree Languages i.e. with Binders and Infinite Symbols?

I'm wondering if there has been any research done into automata that accept languages of trees that can bind arbitrary variables, and are considered equal under alpha equivalence. I've found so far: ...
78 views

### Box stacking problem, and variants

You are given $n$ boxes and want to stack them to make a tallest possible tower, but you can only stack a box on top of another if the base is smaller in both dimensions. This is a classic dynamic ...
198 views

### Can the halting problem be solved probabilistically?

Let $H$ be the halting oracle, meaning that $H$ is a function on pairs of strings such that $H(P,X) = 1$ iff $P$ halts on $X$. A probabilistic program is a program that has (oracle) access to a random ...
15 views

### How to set the proper threshold to remove the features in feature selection? [closed]

With a classification problem with 256 features, I will apply feature selection to find the proper attribute will provide the highest accuracy. How can I set the criteria or threshold for selection of ...
21 views

### A continuum version of the 1D k-means clustering problem: constant factor approximations

Modify the k-means clustering problem in 1D by assuming that, instead of a finite number of observations, we must classify into $K$ clusters a continuum of observations, distributed on the unit ...
153 views

### Is there an equivalent to VC-dimension for density estimation as opposed to classification?

VC-dimension can be used to quantify the capacity for classifier models and compute generalization bounds, but is there an equivalent concept that can be applied to density estimation, e.g. to compute ...
56 views

### Is there any second-order logic finite satisfiability checker?

I know that there are implementations of first-order (finite) satisfiability checking that, given a finite set of axioms, searches for a finite model that satisfies them all. I would like to ask ...
29 views

### Three Clique Sums of Bounded Treewidth and Bounded Genus graphs

This question asks about the forbidden minors of the class of graphs that can be formed by taking three clique sums of planar graphs and bounded treewidth graphs(The class is defined for some constant ...
54 views

### Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)?

The kernel of a parameterized problem $L$ is a reduction $(x,k) \mapsto (x',k')$ such that: $(x,k) \in L \Leftrightarrow (x',k') \in L$ $|x'| \leq f(k)$ for some function $f$ $k' \leq g(k)$ for some ...
75 views
+50

### reordering a DAG with the minimum changes

Consider a DAG $(V,A)$ with an initial permutation $(v_1,v_2,…,v_n)$. We want to arrange the $n$ vertice in topological order while keeping as many vertices as possible. The problem is: Is it NP-hard ...
44 views

### Is every countable, finite-branching LTS bisimilar to a tree?

Let $L$ be a finite set of labels, and let $\mathcal{C}$ be the set of finitely-branching transition systems labeled by $L$ and with a countable set of states. Let $\sim$ denote the bisimulation ...
28 views

### Best approximations of Minimum Dominating Sets in chordal graphs

I am searching results and papers related to the (in)approximability of the Minimum Dominating Set problem in chordal graphs. In particular, what is the best approximation ratio achievable in polytime ...
13 views

### Power of Hyperedge Replacement Grammars (HRGs)

Can HRGs generate languages which equal or include the following graph languages: All (bipartite) graphs of bounded degree All (bipartite) planar graphs of bounded degree All (bipartite) planar ...
88 views

### VC dimension for balanced binary decision trees

What is the VC dimension of all balanced binary decision tree of depth $k$ in $\{0,1\}^d$? Does it depend on depth $k$ or dimension $d$?
74 views

### Phonology and lambda calculus

I wonder whether there is any relationship between lambda calculus and phonology (study of phonemes). Specifically, how one would use the concepts of lambda calculus (typed or untyped) in the study of ...
111 views

### Which are the best universities for a DPhil/PhD in proof theory and automated reasoning?

I'm an undergraduate student studying computer science and I'm interested in doing a PhD after I graduate. I would like to do research in proof theory and automated reasoning, specifically in ...
150 views

### On the usage of Arora and Barak's main lemma in their proof of the PCP theorem

I am a mathematician working toward understanding a proof the the PCP theorem using Arora and Barak's textbook Computational Complexity. I believe I found a few (fixable) errors in Section 22.2, in ...
64 views

### Efficient sampling of primes

Using rejection sampling, it is trivial to construct a Las Vegas algorithm for sampling a uniformly random prime number less than a given $N$. What is known about sampling algorithms that run in worst-...
62 views

### Time complexity of finding chain decomposition of partially ordered set

Given a partially ordered set $P$ with $n=|P|$ and width $w$: -What is the best known complexity (in expectation) for finding a chain decomposition of $w$ chains? -What is the best known complexity (...
32 views

### Arithmetic complexity of exponentiation

I wanna find out whether following pseudocode has an arithmetic complexity of $\mathcal{O}(n^2)$ or $\mathcal{O}(n)$... ...
60 views

### A conjecture on 4-coloring maximal planar graphs

The question/task is to prove/disprove the conjecture below. Let $G$ be a maximal planar graph with a 4-coloring $f$. Let $(a,b,c,d)$ be a cycle in $G$. Let $S$ be the collection of all $a,c$-paths in ...
49 views

### Can we do non-binary maths in computing? [closed]

forgive my lack of basic computer knowledge but, why do we have to use binary representations of numbers in mathematics in computing? I mean it seems like I am being cheated by non-whole number digits ...
53 views

### Deciding whether an arbitrary context-free grammar generates a deterministic push-down automata?

I know that it's undecidable whether an arbitrary context-free grammar is ambiguous, but is it decidable whether that grammar is deterministic? I can't find the answer to this question anywhere on the ...
29 views

### Distinguishing integer functions of similar encoding complexity

Let $f(n) : \mathbb{N} \to \mathbb{N}$ be an integer function and $C(f)$ the minimum number of "symbols" needed to "encode" $f$ in a suitable representation. This representation ...
131 views

### Is modal $\mu$-calculus “equivalent” to bisimulation?

I know that propositional modal $\mu$-calculus $L\mu$ is bisimulation-invariant. However, I'm curious to what degree it captures bisimulation. Q1: Given two labeled transition systems $T_1$, $T_2$ ...
39 views

### Applications of solvability in the λ-calculus

What are applications of solvability / unsolvability, and of operational characterizations of solvability? Solvability In the (untyped pure call-by-name) $\lambda$-calculus, a closed term is said to ...
34 views

### Time complexity of counting the non-prime numbers

So i have a code that i need to find (and proof) the time complexity of it: For ( i = 2 -> N ) For ( j = 2-> sqrt(i)) If(i%j==0) K++ Break; Would really appreciate if someone can help.
199 views

### Two different graph densities: $|E|/|V|$ and $|E|/(|V|-1)$

Let $G=(V,E)$ be a graph. Let $m(G)=|E|$ and $n(G)=|V|$. There are two different density definitions for $G$: $$d_1(G)=\frac{m(G)}{n(G)}$$ and $$d_2(G)=\frac{m(G)}{n(G)-1}.$$ Let $H^* \subseteq G$ be ...
59 views

### Forbidden Subgraph Characterization for Graphs with few Maximal Cliques

Consider the following property of undirected graphs. A graph has the $s$-vertex overlap property if every vertex is contained in at most $s$ maximal cliques. I am interested in forbidden induced ...
107 views

### Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph

So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices. In general case, it is exponential. I am trying to determine whether the ...
85 views

### A possible error in the semantic chapter of the ISO standard for the Z specification notation

I may have found an error in the ISO standards document for the Z specification notation, namely ISO/IEC 13568:2002, "Information technology — Z formal specification notation — Syntax, type ...
60 views

### Upperbound for max degree of k-tree completion

Definitions: For a graph $G$, a $k$-tree completion of $G$ is a $k$-tree obtained by adding edges to $G$ (if $G$ has a $k$-tree completion, $G$ is said to be a partial $k$-tree). The least integer $k$ ...
122 views

### Reference for computing the rank of a matrix in polynomial time

In a recent paper, I need to use the fact that computing the rank of a matrix over the integers has polynomial complexity. Given the context, I don't particularly care about the exact asymptotics, as ...
76 views

### Looking for an online community specializing in the Z specification language, where I can ask questions

Where can I find an online community specializing in the Z specification language, where I can ask specific questions about the ISO standard for Z?
52 views

160 views

### Are Julia sets (theoretically) Turing-complete?

Could any (computational) function be expressed in terms of a Julia set? Is the space of all possible computational functions (which I think is defined by Turing completeness) translatable to the ...
Time is discrete. There are $n$ time-slots and a single job that can be scheduled on one machine of budget $B$. If the job is scheduled at time-slot $t$, then it will consume $c(t)$ units of the ...
### How fast is an equivalent 2-tape TM compared to a $O(n^2)$ 1-tape TM?
In $O(n^2)$ steps, a 1-tape TM can simulate a 2-tape TM that runs for $O(n)$ steps. How fast is an equivalent 2-tape TM known to run compared to a $O(n^2)$ time, 1-tape TM? "Open question" ...