[an error occurred while processing this directive]<title>Department of Computer Science: Computational Complexity</title>
<meta name="keywords"
      content="Department of Computer Science Research Activities Computational Complexity"></meta>
<meta name="description"
      content="Research activities in the area of Computational Complexity"></meta>
<meta property="og:site_name" content="Department of Computer Science"></meta>
<meta property="og:title" content="Computational Complexity"></meta>
<meta property="og:image"
      content="http://www.cs.ox.ac.uk/images/CompSci_logo_landscapeL_rgb_corrected.jpg"></meta>
<meta property="og:url"
      content="http://www.cs.ox.ac.uk/activities/computationalcomplexity/"></meta>
[an error occurred while processing this directive]
<!-- BREADCRUMBS -->
<div class="content-width">
   <ol class="breadcrumb text-uppercase">
      <li>
         <a href="/">Home</a>
      </li>
      <li>
         <a href="/research/">Research</a>
      </li>
      <li>
         <a href="/research/algorithms/">Algorithms and Complexity Theory</a>
      </li>
      <li>
         <a href="/research/algorithms/activities.html">activities</a>
      </li>
      <li class="active">Computational Complexity</li>
   </ol>
</div>
<!-- MOBILE NAVIGATION -->
<div class="content-width space-below mobile-menu-placeholder visible-xs visible-sm"></div>
<!-- COLUMNS -->
<div class="container-fluid content-width">
   <div class="row">
      <div class="col-xs-12 col-md-6 col-md-push-3" id="maincontent">
         <div class="page-title">
            <div class="row">
               <div class="col-xs-12 col-md-12">
                  <h1>Computational Complexity</h1>
               </div>
            </div>
         </div><p>This sub-group investigates structural complexity. We analyse both machine-based and problem-based complexity classes&nbsp;
         and investigate their mutual relationship.</p>
         <div class="row"></div>
      </div>
      <!-- TACTICAL BOXES (Column 3) -->
      <div class="col-xs-12 col-md-3 col-md-push-3 no-print">
         <div class="row">
            <div class="col-xs-12 col-sm-6 col-md-12">
               <div class="panel panel-dark-brown panel-links text-center">
                  <div class="panel-heading clearfix">
                     <h2 class="panel-title panel-title-small text-uppercase">See also</h2>
                     <span class="underbar"></span>
                  </div>
                  <div class="panel-body no-top-padding">
                     <ul>
                        <li style="margin-bottom:0.33em">
                           <a href="/research/algorithms">Algorithms and Complexity Theory</a>
                        </li>
                     </ul>
                  </div>
               </div>
            </div>
            <div class="col-xs-12 col-sm-6 col-md-12">
               <div class="panel panel-dark-brown panel-links text-center">
                  <div class="panel-heading clearfix">
                     <h2 class="panel-title panel-title-small text-uppercase">Projects</h2>
                     <span class="underbar"></span>
                  </div>
                  <div class="panel-body no-top-padding">
                     <ul>
                        <li style="margin-bottom:0.33em">
                           <a href="/projects/ZivnyURF/">Optimisation of Separable Functions</a>
                        </li>
                     </ul>
                  </div>
               </div>
            </div>
            <div class="col-xs-12 col-sm-6 col-md-12">
               <div class="panel panel-dark-brown panel-links text-center">
                  <div class="panel-heading clearfix">
                     <h2 class="panel-title panel-title-small text-uppercase">Completed Projects</h2>
                     <span class="underbar"></span>
                  </div>
                  <div class="panel-body no-top-padding"
                       style="max-height:300px; max-height: 50vh;overflow-y: auto">
                     <ul>
                        <li style="margin-bottom:0.33em">
                           <a href="/projects/DiscreteDomains/">Discrete Domains</a>
                        </li>
                     </ul>
                  </div>
               </div>
            </div>
         </div>
      </div>
      <div class="col-xs-12 col-md-3 col-md-pull-9 side-menu-col">
         <!-- NAVIGATION (Column 1) -->
         [an error occurred while processing this directive]
      </div>
   </div>
</div>
[an error occurred while processing this directive]