All Questions

0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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. ...
0
votes
0answers
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 ...
-2
votes
0answers
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 ...
2
votes
0answers
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 ...
-1
votes
0answers
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?
-5
votes
0answers
21 views

Proof of regular languages [on hold]

Prove that the given language is not regular using the pumping lemma
-3
votes
0answers
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 ...
1
vote
0answers
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 ...
-4
votes
0answers
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 ...
2
votes
1answer
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. ...
-2
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 $$ ...
-4
votes
0answers
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 ...
8
votes
2answers
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 ...
5
votes
2answers
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 ...
0
votes
0answers
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{equation} \begin{split} &\arg\min_{x} \sum_i c^s_i x^s_i + ...
-3
votes
0answers
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 ...
-6
votes
0answers
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. ...
3
votes
0answers
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 ...
-2
votes
0answers
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 ...
3
votes
1answer
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 ...
16
votes
0answers
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 ...
-1
votes
0answers
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 ...
3
votes
0answers
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 ...
2
votes
0answers
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 ...
0
votes
1answer
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): ...
1
vote
0answers
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 ...
11
votes
0answers
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 ...
2
votes
1answer
88 views

Advances in the program verification?

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 ...
1
vote
1answer
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 ...
-1
votes
0answers
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 ...
6
votes
0answers
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 ...
-2
votes
0answers
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 ...
8
votes
0answers
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 ...
-2
votes
0answers
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?
6
votes
1answer
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 ...
0
votes
0answers
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 ...
-2
votes
0answers
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, ...
2
votes
0answers
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 ...
-2
votes
0answers
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: ...
-5
votes
0answers
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 ...
3
votes
1answer
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 ...
-2
votes
0answers
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 ...
4
votes
1answer
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)$?
-2
votes
1answer
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 ...
-4
votes
0answers
24 views

Proof of Attribute of Balanced (1,1)-Biregular Bipartite Graphs [closed]

Prove that if G is a balanced, biregular, bipartite graph, then the edges of G can be partitioned into blocks such that each block is a perfect matching.
6
votes
0answers
64 views

Fully dynamic algorithms for strong components of a directed graph

I'm faced with the problem of maintaining the strong components of a directed graph under insertions/deletions of edges and vertices. As noted in one of the answers to a closely-related question ...

15 30 50 per page