All Questions

4 views

What is the complexity of decision tree complexity?

Given a boolean function $f$ on $n$ bits, how hard is it to determine its decision tree complexity? (I assume the decision tree is simple, i.e., the allowed questions are the bits of the input.) If ...
36 views

Information content of computational problems

The notion of low information content is used to describe sparse sets and tally sets in complexity theory. Such sets can not be $NP$-complete unless $P=NP$. I am not aware of a formal ...
20 views

Turing machine's emptiness is undecidable How? [on hold]

So every Turing recognisable language has an enumerator. If i build a turing machine which uses the enumerator of language $L$ and accept it if it outputs anything and reject if it outputs nothing. ...
19 views

Understanding MA protocol as a variant of TM for small space setting

MA protocol is one of the most basic models of interactive proofs. Merlin is a prover sending a witness $w$ for given input string $x$, and Arthur is a verifier who verifies if $w$ is a positive ...
10 views

cache memory mapping in computer organization

I am having problem in cache memory question.. I am here with providing the solution of question no 4th and 5 th with the doubts i am having regarding it. 1... .... ...Memory location address ...
17 views

Algorithm to find all intersections in set of simplices

What is the fastest known algorithm to detect all intersections amongst a set of $n$ simplices embedded in $\mathbb{R}^d$? In the case where $d=2$ and all simplices are line segments, this problem ...
11 views

Etymology of “relational algebra” and “relational calculus”

Are relational algebra and relational calculus similar to "regular" algebra and calculus? Or why are they named like that?
21 views

Proof of regular languages [on hold]

Prove that the given language is not regular using the pumping lemma
33 views

Find a particular subset not empty of a graph

I have a problem that I don't know how to solve: Every edge of a general graph G = (VERTICES,EDGES) has a real number 0<=val<=1. Every node is indicated with a letter of the alphabet; G does ...
50 views

Characterization of the Set of all s-t-Min-Cut Sets

I would like to know how to answer the following problem: Input: A family of sets $S$ over a universe $U$. Question: Is there a directed flow network $N$ with an edge labeling ...
35 views

Find subsets of nodes in a graph sum of all edges

Is it possible to visit all the cycles in a graph not necessary directed, from the smaller to the bigger in a polynomial time alghoritm? Example of output: ABA = cycle of 2 nodes ABCA = cycle of 3 ...
78 views

Applications of algebraic geometry in Boolean complexity

Representing boolean functions by polynomials or rational functions either perfectly or approximately is an important topic while polynomials and rational functions is the body of algebraic geometry. ...
47 views

How to compare two matrices of size 3x3?

I'm looking for how to compare two matrices of size 3x3 which are the input of the cellular neural network they are originally two images converted to a 3x3 matrices, Actually I want to know if the ...
71 views

Graph theory: definiton of the crown of a graph

I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand: A crown of a ...
53 views

k closest points that belong to a set

This is a question from theory community, but I came across this issue in a practical problem. So just have this in mind. I have a set of real vectors: $$S = \lbrace v_1, \dots, v_n \rbrace$$ ...
27 views

CS Algorithms Connected-components [on hold]

Prove by induction that two vertices are in the same connected compoment if and only if there are in the same set. 1) BaseCase: one vertex (WORKS) 2) Inductive hypothesis. Assume there is a path p ...
144 views

Straight line complexity of monomials

Let $k$ be some field. As usual, for an $f\in k[x_{1},x_{2},\ldots,x_{n}]$ we define $L(f)$ to be the straight-line complexity of $f$ over $k$. Let $F$ be the set of monomials of $f$, namely the ...
125 views

How to judge the definition of computational complexity of reals is natural or suitable?

As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals or the computation models over reals is not in ...
24 views

0-1 min-cost flow with unit-capacity imposed on sets of nodes

I am now trying to solve a 0-1 min-cost flow with unit-capacity imposed on sets of nodes. Formally, the problem is given by \begin{split} &\arg\min_{x} \sum_i c^s_i x^s_i + ...
37 views

Maximum flow problem with both minimum and maximum capacities [on hold]

I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum ...
75 views

DESIGN A FUNCTION OF THE H FAMILY THAT SOLVES THE NP-COMPLETE SUM SUBSET PROBLEM IN O(n) [on hold]

You could help me to review this work please, ... Any contribution is welcome. ...
28 views

Bichromatic all nearest neighbors

Given two finite sets of points, $R, B \subseteq \mathbb{R}^d$, compute a map $f : R \to B$ where: $f(r) = \text{argmin}_{b \in B} |r - b|$ That is $f(r)$ is the closest point in $B$ to the point ...
120 views

How to reduce the computational complexity max algorithm in this specific case

We work over $\mathbb{R}_+^L$. Let $V$ be the set of column vectors whose coordinates take values $0$ or $1$. Thus, $V$ contains $2^L$ vectors. Let $\mathbf{w}(t)$ (in $\mathbb{R}_+^L$) a vector that ...
41 views

Can real-time deterministic multicounter automata recognize the marked palindrome language?

Consider the marked palindrome language which is defined as MPAL=$\{ w\#w^r | w \in \{a,b\}^* \}$. It is easy to recognize MPAL using only a single stack. My question is whether MPAL can be ...
306 views

Why is HAMILTONIAN CYCLE so different from PERMANENT?

A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment $\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$ such ...
30 views

Reducing computational complexity of sorting algorithm in this specific case [duplicate]

We work over $\mathbb{R}^L$. Let $V$ be the set of column vectors whose coordinates take values $0$ or $1$. Thus, $V$ contains $2^L$ vectors. Let $\mathbf{w}(t)$ (in $\mathbb{R}^L$) a vector that ...
73 views

Testing sortedness of a normalized list of $n$ numbers

It is known that testing whether a list of $n$ arbitrary real numbers is $\varepsilon$-close of being sorted (in Hamming distance) has query complexity $\Theta(\log n)$ [1]. It is also easy to show ...
50 views

How to Quantify Entropy in a Data Set

I'm currently creating a program in Java to analysis the pathological cases of Quicksort. Namely, the transition of complexity from O(n^2) to O(nlogn) as a data set gets less ordered. Since Quicksort ...
41 views

Assign each biclique to a distinct left

Given a minimum biclique edge cover, is it always possible to assign each biclique to a distinct left node (which it contains)? ie one such assignment for this graph (from wikipedia): ...
29 views

Common subgraph isomorphism with K vertex [migrated]

I'm looking for subgraph isomorphism of at least K vertex between Graph A and B. I only can come up with the dumbest algorithm, which is: Compute all combination of vertices with length K of Graph ...
144 views

Is it possible to make trapdoor board games?

Motivated partly by this MO question, I am wondering if it's possible to design a board game where there is a simple winning strategy but it's hard to find. For example, the game of picking a random ...
88 views

While trying to check what is the state of art in the formal verification, it seemed to me that there were actually no breakthroughs in decades. For example, here ...
73 views

Hitting set of very restricted linear forms

We say that $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$ is a {-1,0,1}-linear form if $f=\sum_{i\in S}x_{i}-\sum_{i\in T}x_{i}$ where $S,T\subseteq[n]$. A hitting set $H\subseteq\mathbb{Z}^{n}$ for ...
17 views

enrichment heap - count min [on hold]

Think Heap enrichment in such a way as to effectively amortized during the operations were performed: Min, DeleteMin, Insert, CountMin. The last operation is to provide the current number of elements ...
59 views

Approximating a max-cut's intersection with other cuts

For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any ...
21 views

Converting to CFG from a CFL? [migrated]

I am trying to learn CFG.Now to make a CFG from a CFL it is really giving pain to me.Is there any simple rule or steps so that i can easily convert a CFL to CFG.I am trying to solve one problem for ...
88 views

Advances towards proving the Held-Karp conjecture for TSP

I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture. The Held-Karp relaxation is conjectured to have an integrality gap of ...
49 views

Are all cryptography problems reducible to factoring?

Are all cryptography problems reducible to factoring? Would the implementation of Shor's algorithm break cryptography? Or do we have another thing to move onto if quantum computers become available?
67 views

Church-Rosser equivalent for concatenative languages?

Looking at the striking parallels between combinatory logic and concatenative languages makes me wonder how many theorems of the former hold in the latter. The Church-Rosser theorem is particularly ...
37 views

Trying to find polynomial-time algorithms for knapsack-like problems

Consider two related problems: You have n cannisters that must go into m trucks that can each carry k cannisters. You require that no truck becomes overloaded, and for each cannister, there is a ...
14 views

Correct form of a Projection Function

I'm not entirely sure what the correct form of a projection function is. I know it is in the form of P(_2^3) (10, 11, 12) = 11 but for writing a zero function that has to accept one parameter, ...
51 views

What is the strongest known lower bound against SIZE(n)?

What is the best known lower bound against (nonuniform) circuits of size $O(n)$? I understand that we don't know of any explicit functions that need circuits of size more than something like $5n$. But ...
22 views

Tree T in a graph G that isn't normal

I'm trying to figure out what a normal tree actually means, and what I don't understand is how can a tree be not normal. Is it simply that a normal tree T has to contains all vertices of G? EDIT: ...
42 views

Is this statement about NP completeness valid? [closed]

A friend of mine made a statement this morning, which goes as follows: Depiction of Reality without any bias is Reality itself. The problem of depicting Reality without any bias is thus an NP ...
64 views

Approximation algorithms for min vector subset-sum over GF(2)

In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum. Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing ...
22 views

Can we repeat attributes in child classes that are already placed in parent class? [closed]

I am making Class diagram, let Parent Class A have "string Name" , "int id". Question is " In child class we have to mention attribute again "string Name" or not " ? While child class is ...
82 views

On Boolean functions with a certain number of zeros

Given boolean $f(\Bbb x)$, with $\Bbb x\in\{0,1\}^n$, what are good upper/lower bounds, in terms of $|f^{-1}(0)|$, for minimum $deg(p(\Bbb x))$ of a real polynomial satisfying $p(\Bbb x)=f(\Bbb x)$?
37 views

Running time of an algorithm [closed]

I started to learn Computer Science at the university and I struggle with complexity theory. I have no idea how I can measure the amount of steps a certain algorithm written in pseudocode takes. I ...