rotia's user avatar
rotia's user avatar
rotia's user avatar
rotia
  • Member for 9 years, 5 months
  • Last seen more than 6 years ago
7 votes

MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

6 votes

Is this classic puzzle book game NP-complete?

5 votes
Accepted

Can deterministic Turing machine beats/wins (if possible) the "Bombs and Levers" game in polynomial time?

4 votes

How to prove the NP-completeness of 15-Partition Problem

3 votes
Accepted

is this NPC Prob? Minimum count of distinct values at all matrix columns provided only in-row swap operation

2 votes

Is square numbers written in binary a regular language?

2 votes

Prove that checking if context free grammar generates word with all symbols is NP-complete - unclear statement about encoing probem in exercise

2 votes

Degree Reduction in Max Cut and Vertex Cover

2 votes

Given an amount of sets with numbers, find a set of numbers not including any of the given

2 votes
Accepted

In this proof that sokoban+ is pspace complete, how does the gadgets register the fact that a cell of the turing machine has changed?

2 votes
Accepted

Is there a name for graphs which contain oriented and non-oriented edges?

1 vote

How can ships in Battleship be partitioned into B subsets, each with a capacity C?

1 vote

Decision problem which belongs to P reduced to a decision problem which belongs to NP?

1 vote
Accepted

Partition partition with constraint of equal size

1 vote

Showing that M is NP-Complete

1 vote

Understanding transactions

1 vote

Where can I read CS papers?

0 votes

How might neural networks use a symbolic A.I approach?

0 votes

Implement a search procedure in terms of a set test procedure